Level : Codeforces Div-2 D

Coder Coder is fighting a group of n monsters arranged in a straight line. The health of the i-th monster is a_i.

Coder Coder has a special attack that can defeat the monsters one by one. Before starting, he chooses one monster as the starting point.

The attack works as follows:

• On the first move, Coder Coder attacks the chosen monster.
• After that, he can attack any monster that is adjacent to at least one monster that has already been attacked.
• Each monster is attacked exactly once.

If a monster is attacked on the k-th move, Coder Coder needs to have an attack power of at least:

a_i + k - 1

for that monster to be defeated.

Coder Coder wants to choose the starting monster and the attack power optimally so that all monsters can be defeated.

Find the minimum attack power required.

Input

The first line contains a single integer n — the number of monsters.

The second line contains n integers:

a_1, a_2, ..., a_n

where a_i is the health of the i-th monster.

Constraints

• 1 ≤ n ≤ 3 · 10^5
• 1 ≤ a_i ≤ 10^9

Output

Print one integer — the minimum initial attack power Coder Coder needs to defeat all the monsters.

Examples

Example 1

Input

6
2 1 5 6 4 3

Output

8

Example 2

Input

5
4 4 4 4 4

Output

8

Example 3

Input

2
1 1000000000

Output

1000000000