分数: 500 点
问题陈述
有 N AtCoder 街沿线的建筑物,编号 1 通过 N 从西向东。最初,建筑物 1, 2, \ldots, N 的高度为 A_1, A_2, \dots, A_N。
ARC Wrecker, Inc.总裁高桥计划选择整数 l 和 r (1 \leq l \lt r \leq N) 并制作建筑物的高度 l, l+1, \dots, r 全为零。 为此,他可以按任意顺序多次使用以下两种操作:
- 设置一个整数 x (l \leq x \leq r-1) 并增加建筑物的高度 x 和 x+1 by 1 每个。
- 设置一个整数 x (l \leq x \leq r-1) 并降低建筑物的高度 x 和 x+1 by 1 每个。仅当这两座建筑物的高度均为 1 或更大。
请注意,范围 x 取决于 (l,r).
有多少种选择 (l, r) 高桥有什么地方可以实现他的计划吗?
约束
- 2 \leq N \leq 300000
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
打印答案。
示例输入 1
5 5 8 8 6 6
示例输出 1
3
高桥可以实现他的计划 (l, r) = (2, 3), (4, 5), (2, 5).
例如,对于 (l, r) = (2, 5),以下操作顺序使建筑物的高度 2, 3, 4, 5 全为零。
- 降低建筑物的高度 4 和 5 by 1 每次,连续六次。
- 降低建筑物的高度 2 和 3 by 1 每次,连续八次。
对于剩下的七个选择 (l, r),没有任何操作序列可以实现他的计划。
示例输入 2
7 12 8 11 3 3 13 2
示例输出 2
3
高桥可以实现他的计划 (l, r) = (2, 4), (3, 7), (4, 5).
例如,对于 (l, r) = (3, 7),下图展示了一种可能的解决方案。 仅

示例输入 3
10 8 6 3 9 5 4 7 2 1 10
示例输出 3
1
高桥可以实现他的计划 (l, r) = (3, 8) 。
示例输入 4
14 630551244 683685976 249199599 863395255 667330388 617766025 564631293 614195656 944865979 277535591 390222868 527065404 136842536 971731491
示例输出 4
8