Chcesz trenować jazdę na łyżwach na podanej trasie. Składa się ona z punktu startowego, $N$ punktów pośrednich i punktu końcowego. Trening zaczyna się w punkcie startowym z prędkością $0$, prowadzi przez punkty pośrednie od $1$ do $N$ w kolejności rosnących numerów i kończy się po dotarciu do punktu końcowego z prędkością $0$.

Każdy punkt pośredni ma ograniczenie prędkości $V_i$, więc podczas przemieszczania się trzeba dostosować prędkość, aby nie przekroczyć ograniczenia w następnym odwiedzanym punkcie. Prędkość można zwiększyć dowolnie, ale przy zwalnianiu można ją zmniejszyć tylko o $1$ względem prędkości w ostatnio odwiedzonym punkcie. Poza punktem startowym i końcowym prędkość nie może wynosić $0$. Można też utrzymać niezmienioną prędkość.

Wynik treningu jest równy sumie prędkości we wszystkich punktach, więc chcesz go zmaksymalizować. Mając ograniczenia prędkości na trasie, wyznacz największy możliwy wynik treningu na tej trasie.

Na przykład rozważ trasę z trzema punktami pośrednimi o ograniczeniach $V=[2,3,1]$. Jeśli w punkcie pośrednim $2$ utrzymasz prędkość $3$, nie zdołasz dostosować prędkości do co najwyżej $1$ w punkcie pośrednim $3$. Jednym z możliwych treningów są prędkości $[2,2,1]$, których suma wynosi $2+2+1=5$. Inne możliwe treningi to $[1,1,1]$ i $[1,2,1]$, ale ich sumy prędkości nie przekraczają $5$. Największy wynik treningu na tej trasie wynosi zatem $5$.

Ograniczenia

• Wszystkie podane liczby są całkowite.
• $1 \le N \le 500000$
• $1 \le V_i \le 1000000000$ ($1 \le i \le N$)

Podzadania

1. 8 punktów: $N \le 8$, $V_i \le 8$ ($1 \le i \le N$)
2. 12 punktów: $N \le 500$, $V_i \le 500$ ($1 \le i \le N$)
3. 17 punktów: $N \le 5000$, $V_i \le 5000$ ($1 \le i \le N$)
4. 10 punktów: $N \le 5000$
5. 53 punktów: Brak dodatkowych ograniczeń.

Wejście

Pierwszy wiersz zawiera $N$.

Drugi wiersz zawiera kolejno $V_1,V_2,\ldots,V_N$, rozdzielone spacjami.

Wyjście

Wypisz odpowiedź w pierwszym wierszu.

Przykład

Wejście 1

3
2 3 1

Wyjście 1

5

Wejście 2

4
23 7 1 5

Wyjście 2

7