Problem Description

Given an array $a$ of length $n$, find how many triples $i, j, k$ $(1 \leq i < j < k \leq n)$ satisfy $a_k - a_j = a_j - a_i$.

Input Format

The first line contains an integer $n$. The second line contains $n$ positive integers $a_i$.

Output Format

Output one integer in one line, representing the required result.

10
3 5 3 6 3 4 10 4 5 2

9

Hint

Constraints: $1 \leq n \leq 10^5$, $1 \leq a_i \leq 3 \times 10^4$.

Translated by ChatGPT 5