Score: $500$ points

问题陈述

给定一个长度为 $N$ 的序列 $A$，序列中的整数在 $1$ 到 $\textbf{10}$（包括 $1$ 和 $\textbf{10}$）之间。

如果满足以下条件，则称整数对 $(l,r)$ 为一个好对：

• 序列 $(A_l,A_{l+1},\ldots,A_r)$ 包含一个长度为 $3$ 的等差子序列（可以是不连续的）。更准确地说，存在一个整数三元组 $(i,j,k)$，满足 $l \leq i < j < k\leq r$ 且 $A_j - A_i = A_k - A_j$。

找出好对的数量。

以上为大语言模型 kimi 翻译，仅供参考。

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.

Sample Input 1

5
5 3 4 1 5

Sample Output 1

3

There are three good pairs: $(l,r)=(1,4),(1,5),(2,5)$.

For example, the sequence $(A_1,A_2,A_3,A_4)$ contains an arithmetic subsequence of length $3$, which is $(5,3,1)$, so $(1,4)$ is a good pair.

Sample Input 2

3
1 2 1

Sample Output 2

0

There may be cases where no good pairs exist.

Sample Input 3

9
10 10 1 3 3 7 2 2 5

Sample Output 3

3