Стать сильнее
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эйден Колдуолл, чтобы выживать в мире, полном зомби, может временно улучшать свои характеристики, использовав ингибитор из $$$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$$$, ..., $$$a_n$$$ — время, которое каждый компонент должен находиться в устройстве ($$$1 \leqslant a_i \leqslant 10^9$$$).

Выходные данные

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

Система оценки

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

ПодзадачаБаллы Дополнительные ограничения Необходимые подзадачи Информация о проверке
112$$$n \leqslant 3$$$полная
215$$$n \leqslant 7$$$1полная
315 $$$a_i < a_{i+1}$$$ для всех $$$i < n$$$ полная
418$$$a_i$$$ четно для всех $$$i$$$полная
520$$$n \leqslant 1000$$$2полная
620нет1 – 5первая ошибка

Примеры

Входные данные
2
1 2
Выходные данные
2
Входные данные
3
3 6 1
Выходные данные
1
Входные данные
5
1 2 4 3 2
Выходные данные
3

Примечание

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

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

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