与えられたスケートコースで練習をしようとしています。コースは出発地点、$N$ 個の中間地点、到着地点からなります。練習は出発地点から速さ $0$ で出発し、中間地点 $1$ から $N$ までを番号の昇順に訪れ、速さ $0$ で到着地点に着いた後に終了します。

各中間地点には速度制限 $V_i$ があり、次に訪れる地点の速度制限を超えないように移動中に速さを調整しなければなりません。加速時は好きなだけ速くできますが、減速時は最後に訪れた地点での速さから $1$ だけ下げられます。ただし、出発地点と到着地点以外では速さを $0$ にできません。速さを変えずに維持することもできます。

練習の成果は各地点での速さの和に等しいため、これを最大化したいと考えています。コースの速度制限が与えられたとき、そのコースで得られる練習の成果の最大値を求めてください。

例えば、中間地点が 3 個あり、速度制限が $V=[2,3,1]$ の場合を考えます。中間地点 $2$ で速さ $3$ を維持すると、中間地点 $3$ で速さを $1$ 以下に調整できません。可能な練習方法の 1 つは、速さを $[2,2,1]$ とすることで、その和は $2+2+1=5$ です。他にも $[1,1,1]$ や $[1,2,1]$ が可能ですが、それらの速さの和は $5$ を超えません。したがって、このコースで得られる練習の成果の最大値は $5$ です。

制約

• 与えられる数はすべて整数です。
• $1 \le N \le 500000$
• $1 \le V_i \le 1000000000$ ($1 \le i \le N$)

小課題

1. 8 点: $N \le 8$, $V_i \le 8$ ($1 \le i \le N$)
2. 12 点: $N \le 500$, $V_i \le 500$ ($1 \le i \le N$)
3. 17 点: $N \le 5000$, $V_i \le 5000$ ($1 \le i \le N$)
4. 10 点: $N \le 5000$
5. 53 点: 追加の制約はありません。

入力

1 行目に $N$ が与えられます。

2 行目に $V_1,V_2,\ldots,V_N$ がこの順に空白区切りで与えられます。

出力

1 行目に答えを出力してください。

入出力例

入力 1

3
2 3 1

出力 1

5

入力 2

4
23 7 1 5

出力 2

7