Quieres practicar patinaje en un recorrido dado. El recorrido consta de un punto de salida, $N$ puntos intermedios y un punto de llegada. La práctica comienza en la salida con velocidad $0$, visita los puntos intermedios del $1$ al $N$ en orden creciente de número y termina tras alcanzar la llegada con velocidad $0$.

Cada punto intermedio tiene un límite de velocidad $V_i$, así que debes ajustar la velocidad durante el desplazamiento para no superar el límite del siguiente punto que visites. Puedes aumentar la velocidad tanto como quieras, pero al reducirla solo puedes disminuirla en $1$ respecto a la velocidad en el último punto visitado. La velocidad no puede ser $0$ en ningún lugar salvo en la salida y la llegada. También puedes mantenerla sin cambios.

El resultado de la práctica es la suma de las velocidades en todos los puntos, y quieres maximizarlo. Dados los límites de velocidad del recorrido, encuentra el mayor resultado que puedes obtener en él.

Por ejemplo, supón que hay tres puntos intermedios con límites $V=[2,3,1]$. Si mantienes una velocidad de $3$ en el punto intermedio $2$, es imposible ajustarla a como máximo $1$ en el punto intermedio $3$. Una práctica posible usa las velocidades $[2,2,1]$, cuya suma es $2+2+1=5$. Otras prácticas posibles son $[1,1,1]$ y $[1,2,1]$, pero sus sumas no superan $5$. Por tanto, el mayor resultado posible en este recorrido es $5$.

Restricciones

• Todos los números dados son enteros.
• $1 \le N \le 500000$
• $1 \le V_i \le 1000000000$ ($1 \le i \le N$)

Subtareas

1. 8 puntos: $N \le 8$, $V_i \le 8$ ($1 \le i \le N$)
2. 12 puntos: $N \le 500$, $V_i \le 500$ ($1 \le i \le N$)
3. 17 puntos: $N \le 5000$, $V_i \le 5000$ ($1 \le i \le N$)
4. 10 puntos: $N \le 5000$
5. 53 puntos: Sin restricciones adicionales.

Entrada

La primera línea contiene $N$.

La segunda línea contiene $V_1,V_2,\ldots,V_N$, en ese orden, separados por espacios.

Salida

Imprime la respuesta en la primera línea.

Ejemplos

Entrada 1

3
2 3 1

Salida 1

5

Entrada 2

4
23 7 1 5

Salida 2

7