# Problem K

Social Distancing

You are given a array of $n$ numbers $a_1, a_2, \ldots , a_ n$. We are trying to safe distance $n$ people by arranging them in a row. The government has added strange safe distancing rules: when person $i$ and $j$ are adjacent, they should stand $a_{max(i,j)}$ distance apart. Note that there are no restrictions between non-adjacent persons. Find the minimum distance between the leftmost and rightmost person.

## Input

The first line of each test case contains one integer n $(2\leq n\leq 300\, 000)$ — the length of the array.

The second line of each test case contains n integers $a_1,a_2,\ldots ,a_ n$ $(1\leq a_ i\leq 10^9)$ — the array given in the problem.

## Output

Output a single integer — the answer to the problem.

Sample Input 1 | Sample Output 1 |
---|---|

3 1 3 5 |
8 |

Sample Input 2 | Sample Output 2 |
---|---|

3 5 3 1 |
2 |