Hide

Problem KSocial 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

CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show