Arithmetic Subsequences

You are given a permutation of the numbers $1, 2, \ldots, n$ for some $n$. Let the elements of the permutation, in order, form a sequence $a_1, a_2, \ldots, a_n$. Your task is to count how many arithmetic subsequences of $a$ have length exactly $3$. More precisely, count the triples $(i, j, k)$ such that $i < j < k$ and $a_j - a_i = a_k - a_j$.

The first line contains one integer $n$ $(1 \le n \le 200\,000)$. The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ describing the permutation.

Print the number of length-$3$ arithmetic subsequences of the given permutation. You may assume the answer does not exceed $1\,000\,000$.