등차 부분수열

어떤 $n$ 에 대해 $1, 2, \ldots, n$ 을 원소로 하는 순열이 주어진다. 순열의 원소를 나오는 순서대로 $a_1, a_2, \ldots, a_n$ 이라고 하자. 길이가 정확히 $3$ 인 등차 부분수열이 몇 개인지 세는 것이 목표다. 더 정확히 말하면, $i < j < k$ 이면서 $a_j - a_i = a_k - a_j$ 를 만족하는 삼중쌍 $(i, j, k)$ 의 개수를 구하라.

첫째 줄에 정수 $n$ $(1 \le n \le 200\,000)$ 이 주어진다. 둘째 줄에는 순열을 나타내는 $n$ 개의 정수 $a_1, a_2, \ldots, a_n$ 이 주어진다.

주어진 순열에서 길이가 $3$ 인 등차 부분수열의 개수를 출력한다. 답은 $1\,000\,000$ 을 넘지 않는다고 가정해도 된다.