Problem description

Jednym z kroków podczas kolonizacji sąsiednich planet jest sprawdzenie jakie panują na nich warunki atmosferyczne. W tym celu Bajtazar wyhodował bakterię, która każdego dnia dzieli się na dokładnie k identycznych bakterii. Parametr k jest liczbą całkowitą zależną od warunków panujących na planecie, na której aktualnie znajduje się bakteria. W przypadku wyjątkowo złych warunków atmosferycznych bakteria może się w ogóle nie dzielić (wtedy k = 1). Z poczynionych wcześniej obserwacji, Bajtazar wie, że warunki na każdej planecie nigdy się nie zmieniają.

Bajtazarowi udało się już rozesłać na różne planety po pewnej liczbie bakterii. Rozesłał też stacje nadawcze wysyłające codzienne raporty z liczbą bakterii na każdej planecie. Niestety, jak to jednak bywa w kosmosie, aparatura okazała się zawodzić. Nie dość, że niektóre raporty przestały dochodzić do Bajtazara, to jeszcze żadne z nich nie miały informacji z jakiej planety pochodzą, a zdarzało się nawet tak, że pomiary z kilku dni na jednej planecie przychodziły w losowej kolejności.

Bajtazar ma teraz do dyspozycji jeden długi raport, w którym znajdują się kolejne liczności bakterii, jakie udało się zanotować z przychodzących do niego informacji. Teraz jego plan polega na tym, aby wyciąć z niego spójny fragment, w którym znajdą się takie pomiary, które mogły pochodzić z co najmniej trzech kolejnych dni na jednej z planet. Czy jesteś w stanie mu pomóc i odpowiedzieć na ile sposobów może on wybrać taki fragment raportu?

Wejście

W pierwszym wierszu wejścia podana jest jedna liczba całkowita N, oznaczająca długość raportu, jaki udało się uzyskać Bajtazarowi.
W drugim wierszu podane jest N, pooddzielanych pojedynczymi odstępami liczb całkowitych, oznaczających kolejne liczności bakterii w raporcie.

Wyjście

Na wyjściu wypisz jedną liczbę, oznaczającą liczbę przedziałów, które zawierają taki fragment raportu, że znajdują się na nim co najmniej trzy wartości, które mogły być zanotowane na jednej planecie w ciągu kolejnych dni.

Ograniczenia

1 ≤ N ≤ 10⁵, wszystkie liczby w raporcie są z przedziału od 1 do 1 000 000 włącznie.

Przykład

10
3 1 8 15 27 16 2 7 9 4

4