A frog is going to starve to death when God give it some insects. The insects are put inside a line of N plates, and one insect in one plate. At the beginning, the frog can jump into any plate. Then the frog can only jump forward into larger plates. The frog will eat up all food in a plate when it jumps into it. Please help the greedy frog eat as many insects as possible.
Note that the frog can only jump forward .
Input
There are multiple cases ended with EOF. Every case have two lines .
The first number of each case is one number——N (3 <= N <= 100000).
The following N positive integers si (1 <= si <= 1000000000) are the size of N plates.
Output
For each test, output one line containing a single integer——maximum insects the frog can eat.