Tu equipo de cazadores de tesoros acaba de descubrir un sitio arqueológico gigante, lleno de metales preciosos y antigüedades valiosas. El sitio está compuesto por $n$ puntos de excavación en una línea.

Los planes iniciales sugieren que cada uno de los $n$ puntos de excavación tiene un beneficio neto asociado. El beneficio asociado al punto $i$-ésimo es $p_i$. Más específicamente, esto significa que tu equipo ganaría $p_i$ dólares por cada metro excavado en el punto $i$-ésimo. Ten en cuenta que $p_i$ también puede ser negativo, lo que significa que el costo operativo de la maquinaria de excavación supera la ganancia real de excavar en el punto $i$-ésimo.

Naturalmente, querrías excavar tanto como sea posible en los puntos más rentables. Sin embargo, para no causar deslizamientos de tierra, no se permite tener pendientes demasiado pronunciadas. Más precisamente, para dos puntos adyacentes cualesquiera, la diferencia entre la profundidad de excavación en estos puntos no puede diferir en más de 1 metro. En particular, los puntos 1 y $n$ solo pueden excavarse como máximo 1 metro de profundidad.

¿Cuál es el mayor beneficio neto que puedes obtener bajo estas condiciones?

Por ejemplo, un plan de excavación válido que resulta ser óptimo en el caso de la primera entrada de ejemplo se ilustra a continuación. El beneficio neto de dicho plan es 8.

Entrada

La primera línea de la entrada contendrá un número entero positivo $n$ ($1 \le n \le 250\,000$).

La segunda línea de la entrada contendrá $n$ números enteros $p_i$ ($-10^6 \le p_i \le 10^6$), separados por espacios.

Salida

Imprime exactamente un número entero, el mayor beneficio que puedes obtener.

Ejemplos

Entrada 1

5
1 3 -4 2 1

Salida 1

8

Entrada 2

4
1 1 -2 3

Salida 2

5

Entrada 3

5
-1 -3 0 -5 -4

Salida 3

0