Annettuna on taulukko, jossa on n lukua. Tehtäväsi on etsiä taulukosta alitaulukko, jonka lukujen summa on mahdollisimman suuri.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: taulukon koko.

Seuraavalla rivillä on n lukua x_1,x_2,\ldots,x_n: taulukon sisältö.

Tuloste

Ohjelmasi tulee tulostaa suurin alitaulukon summa.

Rajat

• 1 \le n \le 10^5
• -10^9 \le x_i \le 10^9

Esimerkki

Syöte:

5
2 3 -1 5 -2

Tuloste:

9