题目描述

给定一个由 $1$ 到 $10$ 之间的整数构成的长度为 $N$ 的数列 $A$。

对于满足 $1\leq l \leq r \leq N$ 的整数对 $(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$。

请计算良好组的个数。

输入格式

输入通过标准输入按以下格式给出：

$N$ $A_1$ $\ldots$ $A_N$

输出格式

请输出答案。

样例 1

输入

5
5 3 4 1 5

输出

3

样例 2

输入

3
1 2 1

输出

0

样例 3

输入

9
10 10 1 3 3 7 2 2 5

输出

3

说明/提示

限制条件

• $3 \leq N \leq 10^5$
• $1 \leq A_i \leq 10$
• 输入的所有数均为整数

样例解释 1

良好组有 $(l, r) = (1, 4), (1, 5), (2, 5)$ 共 $3$ 个。例如，数列 $(A_1, A_2, A_3, A_4)$ 包含了 $(5, 3, 1)$ 这样一个长度为 $3$ 的等差数列作为子序列，因此 $(1, 4)$ 是良好组。

样例解释 2

也有可能不存在良好组。

由 ChatGPT 4.1 翻译