/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 500 点
問題文
AtCoder 街道には N 棟のビルが建っており、西から順に 1 から N までの番号が付けられています。最初の時点では、ビルの高さはそれぞれ A_1, A_2, \dots, A_N です。
ARC 解体業者の社長である高橋君は、整数 l, r (1 \leq l \lt r \leq N) を選び、ビル l, l+1, \dots, r の高さをすべて 0 にしようと計画しています。この際に、以下の 2 種類の操作を好きな順番で何回でも行うことができます。
- 整数 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 の高さを 0 にできます。
- 「ビル 4, 5 の高さを 1 ずつ減らす」操作を 6 回続けて行う
- 「ビル 2, 3 の高さを 1 ずつ減らす」操作を 8 回続けて行う
残り 7 種類の (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
Score: 500 points
Problem Statement
There are N buildings along the AtCoder Street, numbered 1 through N from west to east. Initially, Buildings 1, 2, \ldots, N have the heights of A_1, A_2, \dots, A_N, respectively.
Takahashi, the president of ARC Wrecker, Inc., plans to choose integers l and r (1 \leq l \lt r \leq N) and make the heights of Buildings l, l+1, \dots, r all zero. To do so, he can use the following two kinds of operations any number of times in any order:
- Set an integer x (l \leq x \leq r-1) and increase the heights of Buildings x and x+1 by 1 each.
- Set an integer x (l \leq x \leq r-1) and decrease the heights of Buildings x and x+1 by 1 each. This operation can only be done when both of those buildings have heights of 1 or greater.
Note that the range of x depends on (l,r).
How many choices of (l, r) are there where Takahashi can realize his plan?
Constraints
- 2 \leq N \leq 300000
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the answer.
Sample Input 1
5 5 8 8 6 6
Sample Output 1
3
Takahashi can realize his plan for (l, r) = (2, 3), (4, 5), (2, 5).
For example, for (l, r) = (2, 5), the following sequence of operations make the heights of Buildings 2, 3, 4, 5 all zero.
- Decrease the heights of Buildings 4 and 5 by 1 each, six times in a row.
- Decrease the heights of Buildings 2 and 3 by 1 each, eight times in a row.
For the remaining seven choices of (l, r), there is no sequence of operations that can realize his plan.
Sample Input 2
7 12 8 11 3 3 13 2
Sample Output 2
3
Takahashi can realize his plan for (l, r) = (2, 4), (3, 7), (4, 5).
For example, for (l, r) = (3, 7), the following figure shows one possible solution.
Sample Input 3
10 8 6 3 9 5 4 7 2 1 10
Sample Output 3
1
Takahashi can realize his plan for (l, r) = (3, 8) only.
Sample Input 4
14 630551244 683685976 249199599 863395255 667330388 617766025 564631293 614195656 944865979 277535591 390222868 527065404 136842536 971731491
Sample Output 4
8