Эйден Колдуолл, чтобы выживать в мире, полном зомби, может временно улучшать свои характеристики, использовав ингибитор из $$$n$$$ компонентов. Компоненты активируются с помощью специального устройства. Одно такое устройство представляет из себя стек, в который можно сначала поместить произвольное количество компонентов, а затем достать их из него строго в обратном порядке. Обратите внимание, что после того, как хотя бы один компонент был вынут из устройства, в него больше нельзя помещать новые компоненты, можно только вынимать оставшиеся.
Чтобы ингибитор сработал,
Разумеется, не всегда достаточно одного такого устройства, чтобы ингибитор мог сработать. Например, когда есть только два компонента с $$$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$$$ компонентов, и ингибитор сработал.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 12 | $$$n \leqslant 3$$$ | полная | |
| 2 | 15 | $$$n \leqslant 7$$$ | 1 | полная |
| 3 | 15 | $$$a_i < a_{i+1}$$$ для всех $$$i < n$$$ | полная | |
| 4 | 18 | $$$a_i$$$ четно для всех $$$i$$$ | полная | |
| 5 | 20 | $$$n \leqslant 1000$$$ | 2 | полная |
| 6 | 20 | нет | 1 – 5 | первая ошибка |
2 1 2
2
3 3 6 1
1
5 1 2 4 3 2
3
Первый пример из условия описан в самом условии.
Один из вариантов распределения компонентов по устройствам в третьем примере выглядит так: