题目描述

给你一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots,A_N)$ 。

请你求出有多少对整数 $(l,r)$ 满足以下条件：

其中，序列 $(x_1,x_2,\dots,x_{|x|})$ 为等差数列，当且仅当存在某个数 $d$ ，使得对于所有 $1 \leq i < |x|$ ，都有 $x_{i+1}-x_i=d$ 。特别地，长度为 $1$ 的序列总是等差数列。

输入格式

第一行包含一个整数 $N$ 。

第二行包含 $N$ 个整数 $A_1,A_2,\dots,A_N$ 。

输出一个整数，表示满足条件的整数对 $(l,r)$ 的数量。

4
3 6 9 3

5
1 1 1 1 1

满足条件的整数对 $(l,r)$ 共有8对： $(1,1)$ 、 $(2,2)$ 、 $(3,3)$ 、 $(4,4)$ 、 $(1,2)$ 、 $(2,3)$ 、 $(3,4)$ 、 $(1,3)$ 。

例如，当 $(l,r)=(1,3)$ 时，子序列 $(A_l,\dots,A_r)=(3,6,9)$ 是等差数列；但当 $(l,r)=(2,4)$ 时，子序列 $(A_l,\dots,A_r)=(6,9,3)$ 不是等差数列。

所有满足 $1 \leq l \leq r \leq 5$ 的整数对 $(l,r)$ 都满足条件。