问题描述

给定长度为 $N$ 的正整数序列 $A = (A_1, A_2, \ldots, A_N)$，求有多少对 $(l, r)$（$1 \le l \le r \le N$）使得 $A_l, A_{l+1}, \ldots, A_r$ 是等差数列（长度 1 默认是）。

输入格式

一行 $N$，第二行 $N$ 个整数 $A_i$。

输出格式

一个整数表示答案。

样例输入 1

4
3 6 9 3

样例输出 1

8

样例输入 2

5
1 1 1 1 1

样例输出 2

15

样例输入 3

8
87 42 64 86 72 58 44 30

样例输出 3

22

评测数据规模

对于 $100\%$ 的数据，$1 \le N \le 2 \times 10^5$，$1 \le A_i \le 10^9$。