Problem description
Jasio niedawno odwiedził park linowy. Stojąc przed drewnianym mostkiem zaczął zastanawiać się, ile osób będzie jeszcze w stanie z niego skorzystać, zanim zostanie on oddany do remontu.
Jasio zna wytrzymałość każdej deski, tzn. ile osób może jeszcze na niej stanąć, zanim ta będzie musiała zostać wyremontowana. Deska, której wytrzymałość wynosi 0, nie musi zostać natychmiastowo wyremontowana, ale nikt więcej nie może już na niej stanąć. Ponadto Jasio zakłada, że każdy gość parku jest na tyle wysportowany, że może wykonać krok, o co najwyżej trzy deski w przód.
Twoim zadaniem jest obliczenie maksymalnej liczby osób, która będzie w stanie przejść przez mostek, zanim ten będzie musiał zostać oddany do remontu. Zakładamy, że każda osoba zaczyna stojąc przed mostkiem, a skończyć powinna za nim.
Wejście
W pierwszym wierszu wejścia znajduje się jedna dodatnia liczba całkowita N, będąca liczbą desek w mostku. W drugim wierszu wejścia znajduje się ciąg A1, A2, …, AN, będący wytrzymałością kolejnych desek.
Wyjście
W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna liczba całkowita, będąca maksymalną liczbą osób, która będzie w stanie przejść przez mostek.
Ograniczenia
3 ≤ N ≤ 500 000, 0 ≤ Ai ≤ 108.
Przykład
| Wejście | Wyjście | Wyjaśnienie |
|
|
Przykładowe ścieżki dwóch osób składają się z desek o numerach: 1, 4 oraz 2, 4, 5. |
| Wejście | Wyjście | |
|
|