L’any 1274, una ombra s’alça sobre el Japó quan la poderosa flota de Khotun Khan arriba a les costes de Tsushima. El cruel general mongol, mestre en la guerra, arrasa tot el que troba al seu pas.

Enmig de la devastació s’aixeca Jin Sakai, l’últim hereu del seu clan i un samurái lligat per l’honor dels seus avantpassats. Ferit però indomable, Jin jura plantar cara al Khan i al seu exèrcit, sabent que el destí de la seva terra i l’esperit del seu poble depèn de la seva força interior.

En la seva aventura, Jin haurà de travessar N zones, cadascuna amb un impacte diferent sobre ell, cada zona pot:

• Aportar-li honor (valor positiu).
• Fer-li perdre moral (valor negatiu).

Però hi ha una norma important en el seu camí:

Jin no pot passar per més de dues zones consecutives.

El que si que pot fer es saltar totes les zones que vulgui.

Entrada

Un enter N – nombre de zones (1 ≤ N ≤ 100 000).

Una seqüència de N valors, on cada valor indica l’efecte de la zona corresponent sobre la força interior de Jin (positiu = guany, negatiu = pèrdua).

Sortida

Un enter que indiqui la força interior màxima que Jin pot acumular seguint les normes del problema.

Exemple d’Entrada 1

6
5 -10 15 40 -5 10

Exemple de Sortida 1

70

Explicació de l’exemple 1

1. Entra a la zona 1 guanya +5
2. Salta la zona 2
3. Entra a la zona 3 guanya +15
4. Entra a la zona 4 guanya +40
5. Salta la zona 5
6. Entra a la zona 6 guanya +10

Força interior total: 5 + 15 + 40 + 10 = 70

Aquesta és la Força interior total que pot aconseguir complint la restricció de no passar mai per més de dues zones consecutives.

Exemple d’Entrada 2

9
-3 20 -8 -2 50 -30 40 -1 10

Exemple de Sortida 2

120

Explicació de l'exemple 2

1. Salta la Zona 1
2. Entra a la Zona 2: guanya +20
3. Salta la Zona 3
4. Salta zona 4
5. Entra a la Zona 5: guanya +50
6. Salta Zona 6
7. Entra a la Zona 7: guanya +40
8. Salta la Zona 8
9. Entra a la Zona 9: guanya +10

Força interior total: 20 + 50 + 40 + 10 = 120

Aquesta és la Força interior total que pot aconseguir complint la restricció de no passar mai per més de dues zones consecutives.