Wstęp do programowania w C++

Bajtek wraz z kolegami pisze swoją pierwszą grę komputerową. Gra jest osadzona w środowisku fantasy i polega na uratowaniu księżniczki. Żeby ją uratować, gracz musi przechodzić labirynty oraz pokonywać potwory.
Gra składa się z N plansz, które trzeba przechodzić po kolei. Każda polega na przejściu labiryntu, na końcu którego znajduje się skrzynia skarbów bądź potwór. Jeśli na końcu planszy znajduje się skrzynia skarbów, gracz ją otwiera i zdobywa pewną liczbę diamentów. Jeśli plansza kończy się potworem, gracz musi go pokonać, żeby ukończyć planszę. Każdy potwór jest bardzo wytrzymały i żeby go pokonać gracz potrzebuje specjalnego miecza, którego może kupić u handlarza, który znajduje się pod koniec każdej planszy. Żeby kupić miecz, gracz musi zapłacić określoną liczbę diamentów. Każdy potwór jest wrażliwy na inny miecz, gracz nie zdobywa diamentów w inny sposób niż przez otwieranie skrzyń oraz nie wydaje ich w inny sposób niż na zakup mieczy. Gracz zaczyna grę z zerową liczbą diamentów.

Gra wyróżnia się spośród innych mechaniką zamiany. Gracz może zamienić każdego potwora w skrzynię skarbów, w której będzie tyle diamentów, ile kosztuje miecz niezbędny do pokonania tego potwora. Gracz może użyć tej możliwości na każdej planszy, która kończy się potworem.

Bajtek zaprojektował już plansze, teraz pracuje nad osiągnięciami. Jedno z planowanych osiągnięć polega na przejściu gry używając najmniejszej liczby zamian. Niestety, Bajtek nie wie, jaka to liczba. Pomóż mu i napisz program, którego będzie mógł użyć, żeby dowiedzieć się, ile najmniej zamian potrzeba do ukończenia gry.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N (1 ≤ N ≤ 500000) określająca liczbę plansz w grze Bajtka.
W drugim (ostatnim) wierszu wejścia znajduje się ciąg N liczb całkowitych Ai (−10^9 ≤ Ai ≤ 10^9) pooddzielanych pojedynczymi odstępami opisujące, jak kończą się kolejne plansze. Jeśli liczba Ai jest nieujemna, to na końcu i-tej planszy znajduje się skrzynia skarbów, która zawiera Ai diamentów. Jeśli Ai jest ujemne, na końcu planszy znajduje się potwór, którego można pokonać tylko mieczem, który kosztuje −Ai diamentów.

Wyjście

Twój program powinien wypisać na wyjście dokładnie jedną nieujemną liczbę całkowitą – minimalną liczbę zamian niezbędną do ukończenia gry.

Ocenianie

Możesz rozwiązać zadanie w kilku prostszych wariantach – niektóre grupy testów spełniają pewne dodatkowe ograniczenia.
Poniższa tabela pokazuje, ile punktów otrzyma Twój program, jeśli przejdzie testy z takim ograniczeniem.

Przykłady

Wejście dla testu lab0a:

6  
5 -3 -7 2 20 -7  

Wyjście dla testu lab0a:

1  

Wyjaśnienie:
Gdyby nie zamienić żadnego potwora na skrzynię skarbów, gra przebiegłaby w sposób następujący:

• Gracz przechodzi pierwszą planszę i otwiera skrzynię skarbów z pięcioma diamentami.
• Gracz przechodzi drugą planszę. Kupuje miecz za trzy diamenty i pokonuje potwora. Pozostają mu dwa diamenty.
• Żeby przejść trzecią planszę, gracz musi kupić miecz za siedem diamentów. Niestety, nie stać go na taki zakup, więc nie jest w stanie ukończyć tej planszy.

Jednym z poprawnych rozwiązań w tym przypadku jest zamienienie potwora z drugiej planszy na skrzynię skarbów.
Wtedy gra toczy się w następujący sposób:

• Gracz przechodzi pierwszą planszę i otwiera skrzynię skarbów z pięcioma diamentami.
• Gracz przechodzi drugą planszę, zamienia potwora na skrzynię skarbów i otwiera ją. W środku są trzy diamenty. Gracz ma ich łącznie osiem.
• Gracz przechodzi trzecią planszę. Kupuje miecz za siedem diamentów i pokonuje potwora. Pozostaje mu tylko jeden diament.
• Gracz przechodzi czwartą planszę i otwiera skrzynię skarbów z dwoma diamentami. Ma ich łącznie trzy.
• Gracz przechodzi piątą planszę i otwiera skrzynię skarbów z dwudziestoma diamentami. Ma ich teraz łącznie aż dwadzieścia trzy.
• Gracz przechodzi szóstą planszę. Kupuje miecz za siedem diamentów i pokonuje potwora. Pozostaje mu szesnaście diamentów.

Inną możliwością ukończenia gry wykonując jedną zamianę, było zamienienie potwora z trzeciej planszy.

Wejście dla testu lab0b:

6  
1 -1 6 0 -4 -2  

Wyjście dla testu lab0b:

0  

Wyjaśnienie:
W tym przypadku gracz będzie miał następujące liczby diamentów po ukończeniu kolejnych plansz: 1, 0, 6, 6, 2, 0. Zatem, nie potrzeba żadnych zamian.