← 返回题目列表

AtCoder · arc170_b

B. 算术级数子序列

中文机器翻译题面 查看原题

分数: 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