28615번 - Стать сильнее 다국어

Эйден Колдуолл, чтобы выживать в мире, полном зомби, может временно улучшать свои характеристики, использовав ингибитор из $n$ компонентов.

Компоненты активируются с помощью специального устройства. Одно такое устройство представляет из себя стек, в который можно сначала поместить произвольное количество компонентов, а затем достать их из него строго в обратном порядке. Обратите внимание, что после того, как хотя бы один компонент был вынут из устройства, в него больше нельзя помещать новые компоненты, можно только вынимать оставшиеся.

Чтобы ингибитор сработал,

1. $i$-й компонент должен находиться в описанном устройстве ровно $a_i$ секунд;
2. между вводом в устройство двух последовательных компонентов должна пройти хотя бы одна секунда;
3. между выниманием из устройства двух последовательных компонентов должна пройти хотя бы одна секунда.

Разумеется, не всегда достаточно одного такого устройства, чтобы ингибитор мог сработать. Например, когда есть только два компонента с $a_1 = 1$ и $a_2 = 2$, если поместить в устройство сначала первый компонент, а потом второй, то не будет возможности вынуть первый спустя одну секунду. А если поместить сначала второй, а затем ровно через секунду первый, то оба компонента придется вынимать одновременно.

Однако, имея несколько таких устройств, всегда можно добиться того, чтобы ингибитор сработал. В частности, в рассмотренном выше примере достаточно двух устройств --- в первое на секунду помещается первый компонент, а во второе на две секунды --- второй.

Эйден хочет узнать, какое минимальное количество описанных устройств ему надо иметь, чтобы корректно применить все $n$ компонентов ингибитора. Помогите ему найти это количество.

В первой строке дано единственное целое число $n$ --- количество компонентов ингибитора ($1 \leqslant n \leqslant 2 \cdot 10^5$).

Во второй строке через пробел перечислены целые числа $a_1$, $a_2$, \ldots, $a_n$ --- время, которое каждый компонент должен находиться в устройстве ($1 \leqslant a_i \leqslant 10^9$).

Выведите единственное целое число --- минимальное количество описанных устройств, которых достаточно, чтобы использовать все $n$ компонентов, и ингибитор сработал.

Первый пример из условия описан в самом условии.

Один из вариантов распределения компонентов по устройствам в третьем примере выглядит так:

1. в первое устройство помещаются компоненты номер $4$ и номер $1$ --- между каждым добавлением или выниманием компонентов пройдет ровно секунда;
2. во второе устройство помещается только компонент номер $2$;
3. в третье устройство помещаются компоненты номер $3$ и номер $5$ --- номер $3$ пробудет в устройстве с нулевой секунды по четвертую, а номер $5$ пробудет в устройстве с первой секунды по третью.