题目描述

AtCoder 街道には $N$ 棟のビルが建っており、西から順に $1$ から $N$ までの番号が付けられています。最初の時点では、ビルの高さはそれぞれ $A_1,\ A_2,\ \dots,\ A_N$ です。

ARC 解体業者の社長である高橋君は、整数 $l,\ r$ $(1\ \leq\ l\ \lt\ r\ \leq\ N)$ を選び、ビル $l,\ l+1,\ \dots,\ r$ の高さをすべて $0$ にしようと計画しています。この際に、以下の $2$ 種類の操作を好きな順番で何回でも行うことができます。

• 整数 $x$ $(l\ \leq\ x\ \leq\ r-1)$ を決めて、ビル $x$・ビル $x+1$ の高さを $1$ ずつ増やす
• 整数 $x$ $(l\ \leq\ x\ \leq\ r-1)$ を決めて、ビル $x$・ビル $x+1$ の高さを $1$ ずつ減らす（この操作は両方のビルの高さが $1$ 以上のときのみ可能）

選べる $x$ の範囲が $(l,r)$ に依存することに注意してください。

高橋君が計画を達成することが可能な $(l,\ r)$ の選び方は何通りあるでしょうか？

输入格式

入力は以下の形式で標準入力から与えられます。

$N$ $A_1$ $A_2$ $\cdots$ $A_N$

输出格式

答えを出力してください。

题目大意

题目描述

---

给出一个长度为 $n$ $(2\le n\le 3\times 10^5)$ 的正整数序列 $A_i$ $(1\le A_i\le 10^9)$，您可以进行以下两种操作：

• 操作 $1$：选定整数 x $(l\le x<r)$，$A_x \leftarrow A_x+1$，$A_{x+1} \leftarrow A_{x+1}+1$

• 操作 $2$：选定整数 x $(l\le x<r)$，$A_x \leftarrow A_x-1$，$A_{x+1} \leftarrow A_{x+1}-1$

您需要保证任意时刻 $A_i$ 非负。求问有多少个数对 $(l,r)$ 满足可以通过任意次操作使得 $A_l,A_{l+1}\ ...\ A_r$ 均为零？操作之间不互相影响。

翻译 by wukaichen888

输入格式

输入共两行，第一行含一个正整数 $n$。

第二行包括 $n$ 个正整数，表示序列。

输出格式

一行，表示答案，行末换行。

样例解释

样例#1

数对 $(2,3),(4,5),(2,5)$ 符合要求。

样例#2

数对 $(2,4),(3,7),(4,5)$ 符合要求。

其中，对于 $(l,r)=(3,7)$，下图为合法方案之一。

5
5 8 8 6 6

3

7
12 8 11 3 3 13 2

3

10
8 6 3 9 5 4 7 2 1 10

1

14
630551244 683685976 249199599 863395255 667330388 617766025 564631293 614195656 944865979 277535591 390222868 527065404 136842536 971731491

8

提示

制約

• $2\ \leq\ N\ \leq\ 300000$
• $1\ \leq\ A_i\ \leq\ 10^9$ $(1\ \leq\ i\ \leq\ N)$
• 入力はすべて整数

Sample Explanation 1

$(l,\ r)\ =\ (2,\ 3),\ (4,\ 5),\ (2,\ 5)$ については、高橋君は目的を達成することができます。 例えば、$(l,\ r)\ =\ (2,\ 5)$ と選ぶとき、例えば以下の順に操作を行うことで、ビル $2,\ 3,\ 4,\ 5$ の高さを $0$ にできます。 - 「ビル $4,\ 5$ の高さを $1$ ずつ減らす」操作を $6$ 回続けて行う - 「ビル $2,\ 3$ の高さを $1$ ずつ減らす」操作を $8$ 回続けて行う 残り $7$ 種類の $(l,\ r)$ の選び方については、どのような操作の手順をとっても、高橋君は目的を達成することができません。

Sample Explanation 2

$(l,\ r)\ =\ (2,\ 4),\ (3,\ 7),\ (4,\ 5)$ については、高橋君は目的を達成することができます。 例えば、$(l,\ r)\ =\ (3,\ 7)$ と選ぶとき、以下の図のように操作を行うことが考えられます。 

Sample Explanation 3

高橋君が目的を達成できるのは、$(l,\ r)\ =\ (3,\ 8)$ のときしかありません。