Se te da un arreglo $A$ de $N$ enteros positivos.

Una operación consiste en elegir un índice $i$ ($1 \le i < N$) tal que $A_i > 0$ y $A_{i+1} > 0$, y luego realizar lo siguiente:

• Disminuir $A_i$ en $1$.
• Disminuir $A_{i+1}$ en $1$.

Puedes realizar esta operación cualquier número de veces (incluyendo cero). Tu objetivo es maximizar la suma de los elementos del arreglo después de realizar las operaciones.

Entrada

La primera línea contiene un entero $N$ ($2 \le N \le 10^5$). La segunda línea contiene $N$ enteros $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^9$).

Salida

Imprime un solo entero: la suma máxima posible de los elementos del arreglo después de realizar cualquier número de operaciones.

Restricciones

• $2 \le N \le 10^5$
• $1 \le A_i \le 10^9$

Ejemplos

Entrada 1

3
1 2 1

Salida 1

4

Entrada 2

5
1 1 1 1 1

Salida 2

3

Nota

En el primer ejemplo, el arreglo es $[1, 2, 1]$. Si no realizamos ninguna operación, la suma es $1+2+1 = 4$. Como la operación disminuye la suma total en $2$, para maximizar la suma debemos realizar la menor cantidad de operaciones posible. En este caso, la suma máxima es $4$ realizando $0$ operaciones.