Fireworks

Time limit1sMemory limit256 MB

Summary

Remove N-2 interior piles one by one; each removal drops the nearest surviving neighbors by 1. Minimize the larger of the two final piles.

Level: Medium7 of 10
Topics: Binary search, Greedy, Array, Implementation
Solved: No attempts yet

Problem

The people of the kingdom of Polymath set off fireworks with fire stones. Today's fireworks show will use $N$ firework piles.

You repeat the following operation exactly $N-2$ times to set off the fireworks.

Choose one firework pile other than the two at the ends.
Set off every firework in that pile.
The exploded pile disappears, and the heights of the nearest remaining piles on its left and right each decrease by 1.

After the fireworks show ends, only two firework piles remain. A pile used in one show cannot be reused, so you want to minimize the larger of the heights of the two remaining piles. Write a program that finds this value.

Input

The first line gives the number of firework piles $N$ . The next line gives the heights of the piles $A_1, A_2, \cdots, A_N$ .

Output

Print the minimum possible value of the larger of the two firework piles left at the end.

Constraints

$3 \le N \le 2 \times 10^5$
$N \le A_i \le 10^9$

Examples2

Example 1
Input
```
5
7 6 8 6 9
```
Expected output
```
6
```
Example 2
Input
```
3
7 7 3
```
Expected output
```
6
```