시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

Masz podaną pewną permutację liczb 1, 2, ..., n dla pewnego n. Niech kolejne liczby permutacji tworzą ciąg a1, a2, ..., an. 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 aj - ai = ak - aj.

입력

W pierwszej linii wejścia znajduje się jedna liczba całkowita n (1 ≤ n ≤ 200 000). Drugi wiersz zawiera n liczb całkowitych a1, a2, ..., an, 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.

예제 입력 1

5
1 5 4 2 3

예제 출력 1

2