8699번 - Podciągi arytmetyczne 다국어

문제

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.

제한

힌트