ARC 拆除者 2

时间限制：2s
空间限制：1024MB

题目描述

有 $N$ 栋从西向东编号为 $1$ 到 $N$ 的建筑，第 $i$ 栋初始高度为 $A_i$。选择整数 $l,r$，满足 $1\le l<r\le N$，只允许对编号在 $[l,r]$ 内的建筑进行以下操作任意多次：

• 选择 $l\le x<r$，把第 $x$、$x+1$ 栋的高度同时增加 $1$；
• 选择 $l\le x<r$，在两栋高度都至少为 $1$ 时，把第 $x$、$x+1$ 栋的高度同时减少 $1$。

求有多少组 $(l,r)$ 能够通过这些操作把区间内所有建筑的高度都变为 $0$。

输入格式

第一行输入整数 $N$，第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出一个整数，表示可行区间数量。

样例输入 1

5
5 8 8 6 6

样例输出 1

3

样例输入 2

7
12 8 11 3 3 13 2

样例输出 2

3

样例输入 3

10
8 6 3 9 5 4 7 2 1 10

样例输出 3

1

样例输入 4

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

样例输出 4

8

数据范围

对于所有数据，$2\le N\le300000$，$1\le A_i\le10^9$。