AT_arc119_c [ARC119C] ARC Wrecker 2

[problemUrl]: https://atcoder.jp/contests/arc119/tasks/arc119_c 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) $ の選び方は何通りあるでしょうか？

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 300000 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ $ (1\ \leq\ i\ \leq\ N) $ - 入力はすべて整数 ### Sample Explanation 1 $ (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) $ の選び方については、どのような操作の手順をとっても、高橋君は目的を達成することができません。 ### Sample Explanation 2 $ (l,\ r)\ =\ (2,\ 4),\ (3,\ 7),\ (4,\ 5) $ については、高橋君は目的を達成することができます。 例えば、$ (l,\ r)\ =\ (3,\ 7) $ と選ぶとき、以下の図のように操作を行うことが考えられます。 !\[ \](https://img.atcoder.jp/arc119/392b686a479008a3dbc3fb36893ed144.png) ### Sample Explanation 3 高橋君が目的を達成できるのは、$ (l,\ r)\ =\ (3,\ 8) $ のときしかありません。