Handshakes

A large company employs $n$ people. The employees are numbered with consecutive integers from $1$ to $n$ in the order they arrive at work each day. No two employees arrive at the same time, so employee $1$ arrives first, employee $2$ arrives second, and so on.

Some pairs of employees are friends, and friendship is symmetric: if employee $i$ considers employee $j$ a friend, then employee $j$ also considers employee $i$ a friend. When an employee arrives at work, he quickly walks around the office and shakes hands with all of his friends who are already in the office, that is, those who arrived before him. It is not known which pairs of employees are friends, but for each employee the number of handshakes he makes each day right after arriving at work is known.

The director of the company wants to talk with one of the employees about the current state of affairs. For this he wants to choose the most socially active person, namely the employee with the most friends. Using the available information, determine the maximum number of friends that one of the employees can have.

The first line of the input contains a single number $n$ ($1 \leq n \leq 200\,000$), the number of employees in the company.

The second line of the input contains $n$ integers $h\_i$ ($0 \leq h\_i < i$). The $i$-th number is the number of handshakes that employee $i$ made right after arriving at work, that is, before employee $i + 1$ arrived.

Print a single number: the maximum possible number of friends of one of the company's employees.

In the first example there is only one pair of employees, and they are friends, as follows from $h\_2 = 1$.

In the second example, if employees $3$, $4$, and $5$ all shook hands with the same employee, then that employee has $3$ friends.