Problem description

Jasio lubi sobie utrudniać życie… Ostatnio udało mu się zrobić zadanie Lider, w którym dla danego ciągu długości N trzeba było wskazać, czy posiada on lidera, czyli element występujący więcej niż $\frac{N}{2}$ razy.

Uznał to zadanie za zbyt proste, by móc wystarczająco cieszyć się z jego rozwiązania. Wymyślił więc trudniejszy problem, który jednak okazał się być ponad jego siły.

Twoim zadaniem jest napisać program, który dla ciągu liczb policzy ile jego spójnych przedziałów (fragmentów od i-tej do j-tej pozycji dla 1 ≤ i ≤ j ≤ N) zawiera jakiegoś lidera.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N – długość ciągu Jasia. W drugim wierszu znajduje się N liczb naturalnych A_i będących kolejnymi wyrazami ciągu.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba całkowita, oznaczająca liczbę spójnych przedziałów wejściowego ciągu, które zawierają jakiegoś lidera.

Ograniczenia

1 ≤ N ≤ 100 000, 1 ≤ A_i ≤ N.

Przykład

3
1 2 3

3

5
4 4 2 2 4

11