题目描述

AtCoder 街上有 $N$ 座建筑，从西到东编号为 $1$ 到 $N$。起初，建筑 $1, 2, \\ldots, N$ 的高度分别为 $A_1, A_2, \\dots, A_N$。

ARC Wrecker 公司的总裁高桥计划选择整数 $l$ 和 $r$ $(1 \\leq l \\lt r \\leq N)$，并将建筑物 $l, l+1, \\dots, r$ 的高度全部变为零。为此，他可以任意次数以任意顺序使用以下两种操作之一：

• 选取整数 $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)$ 有多少个？

约束条件

• $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$ 的高度减少 $1$，共六次。
• 连续将建筑物 $2$ 和 $3$ 的高度减少 $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