Du möchtest auf einer gegebenen Strecke Eislaufen üben. Die Strecke besteht aus einem Startpunkt, $N$ Zwischenpunkten und einem Zielpunkt. Das Training beginnt am Startpunkt mit Geschwindigkeit $0$, besucht die Zwischenpunkte $1$ bis $N$ in aufsteigender Nummernfolge und endet nach dem Erreichen des Zielpunkts mit Geschwindigkeit $0$.

Jeder Zwischenpunkt hat eine Geschwindigkeitsbegrenzung $V_i$. Daher musst du deine Geschwindigkeit unterwegs so anpassen, dass sie die Begrenzung am nächsten besuchten Punkt nicht überschreitet. Du darfst beliebig stark beschleunigen, beim Abbremsen aber die Geschwindigkeit gegenüber der am zuletzt besuchten Punkt nur um $1$ verringern. Außer am Start- und Zielpunkt darf die Geschwindigkeit nirgends $0$ sein. Du kannst sie auch unverändert lassen.

Das Trainingsergebnis ist die Summe der Geschwindigkeiten an allen Punkten, und du möchtest es maximieren. Bestimme anhand der Geschwindigkeitsbegrenzungen der Strecke das größtmögliche Trainingsergebnis auf dieser Strecke.

Betrachte beispielsweise eine Strecke mit drei Zwischenpunkten und den Begrenzungen $V=[2,3,1]$. Wenn du am Zwischenpunkt $2$ die Geschwindigkeit $3$ beibehältst, kannst du sie am Zwischenpunkt $3$ nicht auf höchstens $1$ anpassen. Ein möglicher Trainingsablauf verwendet die Geschwindigkeiten $[2,2,1]$ mit der Summe $2+2+1=5$. Weitere mögliche Abläufe sind $[1,1,1]$ und $[1,2,1]$, deren Summen jedoch $5$ nicht überschreiten. Das größtmögliche Trainingsergebnis auf dieser Strecke ist somit $5$.

Beschränkungen

• Alle gegebenen Zahlen sind ganzzahlig.
• $1 \le N \le 500000$
• $1 \le V_i \le 1000000000$ ($1 \le i \le N$)

Teilaufgaben

1. 8 Punkte: $N \le 8$, $V_i \le 8$ ($1 \le i \le N$)
2. 12 Punkte: $N \le 500$, $V_i \le 500$ ($1 \le i \le N$)
3. 17 Punkte: $N \le 5000$, $V_i \le 5000$ ($1 \le i \le N$)
4. 10 Punkte: $N \le 5000$
5. 53 Punkte: Keine zusätzlichen Beschränkungen.

Eingabe

Die erste Zeile enthält $N$.

Die zweite Zeile enthält $V_1,V_2,\ldots,V_N$ in dieser Reihenfolge, durch Leerzeichen getrennt.

Ausgabe

Gib die Antwort in der ersten Zeile aus.

Beispiele

Eingabe 1

3
2 3 1

Ausgabe 1

5

Eingabe 2

4
23 7 1 5

Ausgabe 2

7