Problem Statement

You are given a sequence $A$ of length $N$ consisting of integers between $1$ and $\textbf{10}$, inclusive.

A pair of integers $(l,r)$ satisfying $1\leq l \leq r\leq N$ is called a good pair if it satisfies the following condition:

• The sequence $(A_l,A_{l+1},\ldots,A_r)$ contains a (possibly non-contiguous) arithmetic subsequence of length $3$. More precisely, there is a triple of integers $(i,j,k)$ with $l \leq i < j < k\leq r$ such that $A_j - A_i = A_k - A_j$.

Find the number of good pairs.

Constraints

• $3 \leq N \leq 10^5$
• $1\leq A_i \leq 10$
• All input numbers are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 \ldots A_N

Output

Print the answer.