En el año 1274, una flota mongola liderada por Khotun Khan lanzó una invasión contra la isla japonesa de Tsushima. Jin Sakai, el último samurái de su clan, se encuentra entrenando arduamente con su katana para vengar a su familia y proteger a su pueblo.

En su gran aventura, Jin deberá superar numerosos desafíos en los que podrá:

• Ganar honor (valores positivos).
• Perder moral (valores negativos).

Sin embargo, Jin no puede visitar más de dos zonas consecutivas, ya que debe conservar su energía para el enfrentamiento final contra Khotun Khan y su ejército.

Aclarar que al igual que tu y yo, Jin no es tonto, si ve que en todas las batallas va a salir perdiendo, su resolución será de 0

Entrada

Un entero N (1 ≤ N ≤ 10^5): el número de zonas en Tsushima. Un array Z de tamaño N donde Z[i] (1 ≤ Z[i] ≤ 10^5) representa el cambio de resolución en la zona i:

• Un valor positivo indica ganancia de resolución.
• Un valor negativo indica pérdida de resolución.

Salida

Un entero que indique la resolución máxima acumulada que Jin puede alcanzar al final del camino.

Ejemplo de Entrada

6
5 -10 15 40 -5 10

Ejemplo de Salida

70

Explicación

Jin puede elegir este recorrido:

1. Comienza en la zona 1 (+5).
2. Salta la zona 2 y continúa a la zona 3 (+15).
3. Avanza a la zona 4 (+40).
4. Salta la zona 5 y termina en la zona 6 (+10).

Resolución total: 5 + 15 + 40 + 10 = 70.