시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

В одной крупной компании работает $n$ сотрудников. Сотрудники компании пронумерованы последовательными целыми числами от $1$ до $n$ в порядке, в котором они ежедневно приходят на работу. Никакие два сотрудника не приходят на работу одновременно, таким образом, первым приходит сотрудник с номером $1$, вторым приходит сотрудник с номером $2$ и так далее.

Некоторые пары сотрудников являются друзьями, при этом отношение дружбы симметрично, то есть если сотрудник с номером $i$ считает своим другом сотрудника с номером $j$, то и сотрудник с номером $j$ считает своим другом сотрудника с номером $i$. Известно, что когда очередной сотрудник приходит на работу, он быстро обходит весь офис и жмёт руку всем своим друзьям, уже находящимся в офисе, то есть тем, кто пришёл раньше него. Неизвестно, какие именно пары сотрудников являются друзьями, но для каждого сотрудника известно количество рукопожатий, которое он ежедневно совершает сразу после своего прихода на работу.

Директор компании хотел бы побеседовать с кем-нибудь из сотрудников о текущем состоянии дел. Для этого он хочет выбрать наиболее социально активного человека, а именно сотрудника с максимальным количеством друзей. По имеющейся информации определите, какое максимальное количество друзей может быть у одного из сотрудников. 

입력

В первой строке входных данных записано единственное число $n$ ($1 \leq n \leq 200\,000$) --- количество сотрудников в компании.

Во второй строке входных данных записаны $n$ целых чисел $h_i$ ($0 \leq h_i < i$) --- $i$-е число соответствует количеству рукопожатий, которое совершил сотрудник с номером $i$ сразу после своего прихода на работу, то есть до прихода сотрудника с номером $i + 1$.

출력

Выведите единственное число --- максимально возможное количество друзей у одного из сотрудников компании.

예제 입력 1

2
0 1

예제 출력 1

1

예제 입력 2

5
0 0 1 1 1

예제 출력 2

3

힌트

В первом примере есть всего одна пара сотрудников, и они, как следует из того, что $h_2 = 1$, являются друзьями.

Во втором примере, если все сотрудники $3$, $4$ и $5$ здоровались с одним и тем же сотрудником, то у этого сотрудника $3$ друга.