Arithmetic Progression Subsequence

时间限制：2s
空间限制：1024MB

题目描述

给定一个长度为 $N$、元素均在 $1$ 到 $10$ 之间的整数序列 $A$。

称一对整数 $(l,r)$ 为好区间，当且仅当 $1\le l\le r\le N$，并且 $A_l,A_{l+1},\ldots,A_r$ 含有一个长度为 $3$ 的等差子序列。也就是说，存在 $l\le i<j<k\le r$，满足

求好区间的数量。

输入格式

第一行输入整数 $N$。

第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出好区间的数量。

样例输入 1

5
5 3 4 1 5

样例输出 1

3

样例输入 2

3
1 2 1

样例输出 2

0

样例输入 3

9
10 10 1 3 3 7 2 2 5

样例输出 3

3

数据范围

• $3\le N\le 10^5$；
• $1\le A_i\le 10$；
• 输入中的所有数均为整数。