Друзья
(Время: 2 сек. Память: 32 Мб Сложность: 27%)
В одном классе учится N мальчиков, все они приходят в школу в определенном порядке. Тот, кто приходит первым имеет номер 1, кто приходит вторым – номер 2 и так далее. Последний пришедший имеет номер N.
Некоторые пары ребят описанного выше класса являются друзьями. Причем очевиден тот факт, что если Петя дружит с Васей, то и Вася дружит с Петей. Известно, что когда очередной школьник заходит в класс, то он обходит всех своих друзей и жмет им руку. При этом нам неизвестно кто именно с кем дружит, но достоверно известно: сколько каждый мальчик делает рукопожатий при входе в класс.
Классный руководитель решил выяснить: кто из ребят наиболее социально активен (имеет наибольшее количество друзей). По имеющейся информации необходимо определить какое максимальное количество друзей может быть у одного из ребят.
Входные данные
В первой строке входного файла INPUT.TXT записано единственное число N (1 ≤ N ≤ 200 000) – количество мальчиков в классе.
Вторая строка содержит N целых чисел hi (0 ≤ hi < i) – i-е число соответствует количеству рукопожатий, которое совершил школьник с номером i сразу после своего прихода в школу, то есть до прихода следующего школьника с номером i+1.
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
0 1 1 | 2 |
Пояснение к примеру
Если оба школьника с номерами 2 и 3 поздороваются с первым, то окажется, что у него два друга.
Система оценки
Решения, работающие только для N ≤ 1000, будут оцениваться в 50 баллов.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
