Задача D. Стаканчики ≡

Условие

При подготовке пакета были использованы материалы сайта школьных олимпиад по информатике.

С самого раннего детства Маша мечтала облететь весь земной шар и побывать в разных странах. И вот наконец-то её мечта сбылась — ей предложили работу в одной из крупнейших авиакомпаний мира. Теперь Маша работает стюардессой. В её обязанности входит разносить еду и напитки пассажирам, а также собирать использованную посуду.

Использованные стаканчики Маша собирает следующим образом. Если пассажир не допил напиток, то Маша ставит его стаканчик в новую отдельную стопку. Если же стаканчик пуст, она ставит его в низ самой маленькой стопки (просто вкладывая эту стопку в пустой стаканчик), так как слишком высокую стопку легко уронить (пустой стаканчик ставится в отдельную стопку, только если поднос пуст).

Перед началом сбора использованной посуды Маша знает, сколько напитка в стакане осталось у каждого пассажира. Теперь ее интересует вопрос — сможет ли она донести поднос со стаканчиками, не уронив его. Для этого ей необходимо знать высоту самой большой стопки. Но так как пассажиров очень много, она не может посчитать это сама, поэтому просит вас помочь ей!

Решения, корректно работающие для n ≤ 1000 будут оцениваться из 40 баллов.

В примере в итоге получится одна стопка из первых трех стаканчиков и стопка из последних двух.

Формат входного файла

В первой строке входного файла задано единственное целое число n — количество пассажиров (1 ≤ n ≤ 10⁶).

В следующей строке через пробел заданы n целых чисел a_i — количество оставшегося напитка в стаканчиках (0 ≤ a_i ≤ 10⁹) в том порядке, в котором Маша будет их собирать. Пустому i-ому стакачику соответствует a_i = 0.

Формат выходного файла

В выходной файл выведите единственное целое число — количество стаканчиков в самой большой стопке.

Примеры тестов

5
1 0 0 2 0

3