/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君の前に N 本の柱が一列に並んでいます。左から i 番目の柱の耐久値は A_i です。
高橋君はすべての柱に対して同時に同じ力 X で衝撃を与えます。衝撃を受けた各柱は、耐久値が X だけ減少します。
その後、左から右へ順に連鎖が伝わります。具体的には、柱が倒壊（耐久値が 0 以下になること）すると、すぐ右隣の柱の耐久値がさらに 1 減少します。これにより右隣の柱も倒壊した場合、同様にそのさらに右隣の柱の耐久値が 1 減少します。この連鎖は右方向に、柱が倒壊しなくなるまで続きます。なお、最も右の柱が倒壊しても、それ以上の連鎖は発生しません。
まとめると、各柱が倒壊するかどうかは、直接受ける衝撃 X に加え、すぐ左隣の柱が倒壊していればさらに 1 のダメージを受ける、という規則で左から順に決まります。
すべての柱を倒壊させるために必要な X の最小値を求めてください。X は正の整数とします。
制約
- 1 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で与えられます。
N A_1 A_2 \ldots A_N
- 1 行目には、柱の本数 N が与えられます。
- 2 行目には、各柱の耐久値を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられます。
出力
すべての柱を倒壊させるために必要な力 X の最小値を 1 行で出力してください。
入力例 1
4 2 3 2 4
出力例 1
3
入力例 2
5 5 2 2 2 2
出力例 2
5
入力例 3
12 4 2 5 3 6 7 3 8 4 9 5 10
出力例 3
9
入力例 4
30 8 12 9 13 10 14 11 15 12 16 13 17 14 18 15 19 16 20 17 21 18 22 19 23 20 24 21 25 22 26
出力例 4
25
入力例 5
1 1000000000
出力例 5
1000000000
Score : 300 pts
Problem Statement
There are N pillars lined up in a row in front of Takahashi. The durability of the i-th pillar from the left is A_i.
Takahashi simultaneously applies the same force X to all pillars. Each pillar that receives the impact has its durability decreased by X.
After that, a chain reaction propagates from left to right. Specifically, when a pillar collapses (its durability becomes 0 or less), the durability of the pillar immediately to its right decreases by an additional 1. If this causes the right neighbor to also collapse, the durability of the pillar immediately to its right decreases by 1 as well. This chain continues to the right until a pillar does not collapse. Note that if the rightmost pillar collapses, no further chain reaction occurs.
In summary, whether each pillar collapses is determined from left to right by the following rule: in addition to the direct impact X, a pillar receives an additional 1 damage if the pillar immediately to its left has collapsed.
Find the minimum value of X required to collapse all pillars. X must be a positive integer.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 1 \leq A_i \leq 10^9
- All inputs are integers
Input
The input is given in the following format.
N A_1 A_2 \ldots A_N
- The first line gives the number of pillars N.
- The second line gives N integers A_1, A_2, \ldots, A_N representing the durability of each pillar, separated by spaces.
Output
Print the minimum value of the force X required to collapse all pillars in a single line.
Sample Input 1
4 2 3 2 4
Sample Output 1
3
Sample Input 2
5 5 2 2 2 2
Sample Output 2
5
Sample Input 3
12 4 2 5 3 6 7 3 8 4 9 5 10
Sample Output 3
9
Sample Input 4
30 8 12 9 13 10 14 11 15 12 16 13 17 14 18 15 19 16 20 17 21 18 22 19 23 20 24 21 25 22 26
Sample Output 4
25
Sample Input 5
1 1000000000
Sample Output 5
1000000000