Pelaat peliä, jossa kuljet avaruusaluksellasi n planeetan kautta. Jokaisella planeetalla joko saat tietyn määrää kultaa tai joudut luovuttamaan tietyn määrän kultaa.

Aluksessasi on kultasäiliö, jolla on tietty maksimikoko. Jos saat jollain planeetalla enemmän kultaa kuin säiliöösi mahtuu, joudut jättämään yli menevän kullan planeetalle.

Jos tulet planeetalle etkä voi luovuttaa vaadittua määrää kultaa, planeetan asukkaat tuhoavat aluksesi ja häviät pelin.

Pelin alussa sinulla ei ole yhtään kultaa. Kuinka suuri on pienin kultasäiliö, jonka avulla pääset pelin läpi?

Syöte

Syötteen ensimmäisellä rivillä on yksi kokonaisluku n: planeettojen määrä.

Seuraavalla rivillä on n kokonaislukua p_1,p_2,\ldots,p_n. Jos luku on positiivinen, saat niin paljon kultaa. Jos luku on negatiivinen, menetät niin paljon kultaa.

Tuloste

Tulosta yksi kokonaisluku: pienin mahdollinen kultasäiliön koko. Jos et voi mitenkään päästä peliä läpi, tulosta luku -1.

Rajat

• 1 \le n \le 5 \cdot 10^5
• -10^9 \le p_i \le 10^9

Esimerkki

Syöte:

5
2 3 -1 1 -3

Tuloste:

3