Masz podaną pewną permutację liczb 1, 2, ..., n dla pewnego n. Niech kolejne liczby permutacji tworzą ciąg a₁, a₂, ..., a_n. Twoim zadaniem jest policzenie, ile istnieje arytmetycznych podciągów ciągu a o długości równej 3. Dokładniej, musisz zliczyć trójki i, j, k takie że i < j < k oraz a_j - a_i = a_k - a_j.

입력 형식

W pierwszej linii wejścia znajduje się jedna liczba całkowita n (1 ≤ n ≤ 200 000). Drugi wiersz zawiera n liczb całkowitych a₁, a₂, ..., a_n, reprezentujących naszą permutację.

출력 형식

Na wyjściu należy wypisać liczbę podciągów arytmetycznych o długości 3 dla permutacji z wejścia. Możesz założyć, że wynik nie przekroczy 1 000 000.

예제 입력

5
1 5 4 2 3

예제 출력

2