CNU10 | Progresie

Cerință

Se da un sir de $N$ valori $A_1, A_2, ..., A_N$. Calculati numarul de perechi $(St,Dr)$ bune.
O pereche $(St,Dr)$ este buna daca $St \leq Dr$ si exista cel putin $3$ valori $(i,j,k)$, a.i, $St \leq i < j < k \leq Dr$ si $A_j - A_i = A_k - A_j$ (adica sa fie in progresie aritmetica)

Date de intrare

Pe prima linie este $N$ iar pe al doilea rand este sirul de $N$ valori.

Date de ieșire

Numarul de perechi cerute.

Restricții și precizări

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10$

Exemplul 1

stdin

5
5 3 4 1 5

stdout

3

Explicație

Perechile sunt $(1,4),(1,5),(2,5)$.
De exemplu pentru perechea $(1,4)$ putem alege valorile $5,3,1$ care sunt in progresie aritmetica.

Exemplul 2

stdin

9
10 10 1 3 3 7 2 2 5

stdout

3