题目描述

---

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

样例 1

输入

5
5 8 8 6 6

输出

3

样例 2

输入

7
12 8 11 3 3 13 2

输出

3

样例 3

输入

10
8 6 3 9 5 4 7 2 1 10

输出

1

样例 4

输入

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

输出

8