该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题陈述

强哥在研究一个神秘的数字序列 $A=(A_1,A_2,\dots,A_N)$，他发现这个序列中隐藏着许多等差数列的密码。现在，强哥的任务是找出有多少对整数 $(l,r)$ 满足以下条件：

1. $1\leq l\leq r\leq N$。
2. 子序列 $(A_l,A_{l+1},\dots,A_r)$ 是一个等差数列。

特别地，长度为 $1$ 的子序列总是等差数列。

强哥需要你帮助他快速计算出满足条件的 $(l,r)$ 对数，才能破解这个数字序列的奥秘。

数据范围

• $1\leq N \leq 2\times 10^5$
• $1\leq A_i \leq 10^9$
• 所有输入均为整数

输入

输入通过标准输入，格式如下。

$N$

$A_1$ $A_2$ $\dots$ $A_N$

输出

输出答案。

4
3 6 9 3

8

满足条件的一对整数 $(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)$ 不满足条件，因为它不是等差数列。

5
1 1 1 1 1

15

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