T4 小 Z 的等差数列问题

• 时间：1s

• 空间：256M

题目描述

小 Z 最近在上数学课时学到了等差数列。他发现，等差数列是从第二项起，每一项与前一项的差相等的一种数列，而这个相等的差值被称为公差。例如，数列 1, 5, 9, 13 就是一个公差为 4 的等差数列。

对于一个给定的长度为 $n$ 的整数序列 $a_1, a_2, ..., a_n$，小 Z 认为连续元素个数大于 $2$ 个以上的子段组成的的等差数列才有意义。

小 Z 想知道对上述的整数序列中有多少个这种有意义的子段？

输入格式

输入共两行：

第一行，一个正整数 $n$，表示给定序列长度

第二行，$n$ 个整数，分别表示序列的每一项 $a_1,a_2,...,a_n$

输出格式

输出一个整数，表示满足条件的子段个数。

样例

10
-1 1 3 3 3 2 3 2 1 0

5

说明/提示

样例 1 解释

满足条件的等差数列子段如下：

子段 [1, 3]：数列为 -1, 1, 3，公差为 2。
子段 [3, 5]：数列为 3, 3, 3，公差为 0。
子段 [7, 10]：数列为 3, 2, 1, 0，公差为 -1。
子段 [7, 9]：数列为 3, 2, 1，公差为 -1。
子段 [8, 10]：数列为 2, 1, 0，公差为 -1。

数据范围

对于 $30\%$ 的数据， $1 \leq n \leq 100$

对于 $60\%$ 的数据， $1 \leq n \leq 10^4$

对于 $100\%$ 的数据， $1 \leq n \leq 10^5$ , $-10^9 \leq a_i \leq 10^9$