The Monkey and the Oiled Bamboo

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

Rungs are at strictly increasing heights $r_i$. Start at height 0 with integer strength $k$. A jump larger than current strength fails; a jump exactly equal to it succeeds and then decreases strength by one; a smaller jump leaves strength unchanged. Find the minimum initial $k$.

Input

The first line contains $n$. The second line contains rung heights.

Output

Print the minimum initial strength.

Subtasks

• Subtask 1 — 20%: $n\le10$.
• Subtask 2 — 30%: $n\le5000$.
• Subtask 3 — 50%: $n\le10^5$, $r_n\le10^7$.

Example

Input

5
1 6 7 11 13

Output

5

Explanation

Strength 5 handles jumps 1,5,1,4,2 with decrements after exact jumps.