Problem description

Kuba był podróżnikiem z zamiłowania. Lubił zwiedzać odległe zakątki świata.

Pewnego razu wracając do rodzinnego miasta Wrocławia, ze swojej kolejnej niezwykle ciekawej wyprawy, spotkała go niemiła niespodzianka. Pociąg, którym jechał, wykoleił się. Wzbudziło to jego ogromną niechęć do dalekich podróży i postanowił, że od teraz będzie zwiedzał tylko lokalne atrakcje, korzystając wyłącznie z niezwykle szybkiej i niezawodnej tramwajowej linii 13 wrocławskiego MPK. Trasa tej linii rozpoczyna się niedaleko miejsca zamieszkania Kuby, prowadzi przez cały Wrocław i kończy się nieopodal fabryki czekolady, której smak jest mu szczególnie bliski. Co ciekawe trasa ta nigdy się ze sobą nie przecina, a tramwaj jeździ po niej tylko w jedną stronę, więc Kuba do domu wraca pieszo.

Kuba w trakcie powrotów lubi słuchać swojej ulubionej playlisty posiadającej N utworów, dokładnie tyle ile przystanków ma trasa linii 13. Ostatnio postanowił, że będzie jej słuchał również za każdym razem, gdy będzie jechał tramwajem linii 13, by umilić sobie czas spędzony w bardzo przytulnym środku transportu. Dlatego, że nie jest on człowiekiem konwencjonalnym, to będzie to robił w sposób specyficzny. Przypisał on sobie do każdego przystanku piosenkę, która najbardziej mu się z nim kojarzy i której zawsze będzie słuchał, przejeżdżając przez ten przystanek, a także wsiadając czy wysiadając z niego. Jako iż Kuba lubi niektóre piosenki bardziej niż inne, to przyporządkował każdej pewną liczbę punktów od 1 do N, oznaczającą to, jak bardzo lubi daną piosenkę. Kuba jest człowiekiem kultury i sztuki, co powoduję, że zawsze jest w stanie stwierdzić który utwór mu się bardziej podoba (nie ma dwóch utworów, które podobają mu się tak samo).

Ostatnio nic ciekawego nie działo się w życiu Kuby, a dni wydawały mu się dosyć monotonne, więc wpadł na genialny pomysł jak urozmaicić sobie życie. Postanowił, że przejedzie wszystkie ekscytujące trasy linii 13. Jako ekscytującą trasę uznał tę, w trakcie której najlepsza piosenka, jaką odsłucha, będzie równie dobra, jak piosenki, których będzie słuchał, wsiadając i wysiadając do tramwaju. Piosenka jest tak samo dobra, jak dwie inne, gdy ich sumy punktów są równe (tzn. piosenka, która podoba się Kubie na 3 punkty, jest równie dobra, jak suma tych, które podobają mu się na 2 punkty i na 1 punkt). Kuba zastanawia się ile takich ekscytujących przejazdów, będzie mógł wykonać. Niestety nie wie jak to policzyć i dlatego poprosił cię o pomoc.

Napisz program, który wczyta liczbę piosenek znajdujących się na playliście, oraz ich wartości punktowe i wypisze liczbę ekscytujących tras, które Kuba może przejechać.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba N oznaczająca liczbę piosenek znajdujących się na playliście. W kolejnym wierszu znajduje się N liczb, pooddzielanych pojedynczymi odstępami, oznaczających wartość punktową utworu słuchanego przez Kubę na i-tym przystanku.

Wyjście

W pierwszym (jedynym) wierszu standardowego wyjścia należy wypisać jedną liczbę, oznaczającą liczbę ekscytujących tras, które Kuba może przejechać.

Ograniczenia

3 ≤ N ≤ 500 000.

Podzadania

Przykład

3
1 3 2 

1