Se dă un șir a1, a2, …, an de numere întregi. Definim suma unei secvențe ai, ai+1, …, aj ca fiind suma elementelor sale, adică ai + ai+1 + ... + aj.

Cerința

Să se determine suma maximă posibilă care se poate obține din două secvențe disjuncte din șir.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi șirul de n numere întregi, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul S, reprezentând suma maximă care se poate obține din două secvențe disjuncte.

Restricții și precizări

• 2 ≤ n ≤ 100.000
• -100 ≤ a[i] ≤ 100
• Două secvențe sunt disjuncte dacă nu au niciun element comun.

Exemplul 1:

Intrare

6
2 -1 3 -8 4 -5

Ieșire

8

Explicație

Cele două secvențe care dau suma maximă sunt 2 -1 3 și 4.

Exemplul 2:

Intrare

4
1 2 3 4

Ieșire

10

Explicație

Secvențele pot fi 1 2 și 3 4.