AT_arc119_c.[ARC119C] ARC Wrecker 2

---

给出一个长度为 $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)$，下图为合法方案之一。