ml2 | Picnic’s Table

Filippo is organizing a picnic with his friends, and he is planning where to go. He really likes the park next to his house, but the ground is so bumpy he needs to inspect it carefully for finding the best place.

The park is a narrow strip of land of negligible width, and Filippo measured the height $H_i$ of $N$ points one meter apart. He wants to buy a long table to place on the ground, such that it lays completely horizontal and is held by at least two points on the floor.

In order to be stable enough, the table should rest on at least one point strictly before the middle of the table, and at least one point strictly after the middle of the table. In particular, the table should start at an integer coordinate and end at an integer coordinate. Furthermore, the table cannot extend past the start or the end of the park.

How long is the longest table Filippo can use?

Input data

The first line contains the only integer $N$. The second line contains $N$ integers $H_i$.

Output data

You need to write a single line with an integer: the length of the longest table Filippo can use.

Constraints and clarifications

• $1 \leq N \leq 10 \ 000 \ 000$;
• $1 \leq H_i \leq 10^9$;

Example 1

stdin

7
3 5 3 0 3 2 2

stdout

4

Explanation

In the first sample case the table can be at most $4$ meters long. If it had been extended one more unit to the right, it wouldn’t be balanced anymore

Example 2

stdin

5
1 1 5 5 5

stdout

4

Explanation

In the second sample case the table cannot be extended further to the right because it cannot exceed the limits of the park.