分数: 500 点
问题陈述
给你一个序列 A 长度 N 由之间的整数组成 1 和 \textbf{10},包括在内。
一对整数 如果 (l,r) 满意 1\leq l \leq r\leq N 满足以下条件,则称为好对:
- 序列 (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.
找出好对的数量。
约束
- 3 \leq N \leq 10^5
- 1\leq A_i \leq 10
- 所有输入数字均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 \ldots A_N
输出
打印答案。
示例输入 1
5 5 3 4 1 5
示例输出 1
3
有三对不错的: (l,r)=(1,4),(1,5),(2,5).
例如,序列 (A_1,A_2,A_3,A_4) 包含长度为的算术子序列 3,即 (5,3,1),所以 (1,4) 是一对好搭档。
示例输入 2
3 1 2 1
示例输出 2
0
可能存在不存在良好配对的情况。
示例输入 3
9 10 10 1 3 3 7 2 2 5
示例输出 3
3