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