201192: [AtCoder]ARC119 C - ARC Wrecker 2

Memory Limit：1024 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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

Input

题意翻译

### 题目描述 --- 给出一个长度为 $n$ $(2\le n\le 3\times 10^5)$ 的正整数序列 $A_i$ $(1\le A_i\le 10^9)$，您可以进行以下两种操作： - 操作 $1$：选定整数 x $(l\le x<r)$，$A_x \leftarrow A_x+1$，$A_{x+1} \leftarrow A_{x+1}+1$ - 操作 $2$：选定整数 x $(l\le x<r)$，$A_x \leftarrow A_x-1$，$A_{x+1} \leftarrow A_{x+1}-1$ **您需要保证任意时刻 $A_i$ 非负**。求问有多少个数对 $(l,r)$ 满足可以通过任意次操作使得 $A_l,A_{l+1}\ ...\ A_r$ 均为零？操作之间不互相影响。 翻译 by wukaichen888 ### 输入格式 输入共两行，第一行含一个正整数 $n$。 第二行包括 $n$ 个正整数，表示序列。 ### 输出格式 一行，表示答案，行末换行。 ### 样例解释 #### 样例#1 数对 $(2,3),(4,5),(2,5)$ 符合要求。 #### 样例#2 数对 $(2,4),(3,7),(4,5)$ 符合要求。 其中，对于 $(l,r)=(3,7)$，下图为合法方案之一。 ![](https://img.atcoder.jp/arc119/392b686a479008a3dbc3fb36893ed144.png)

Source/Category

加入题单

算法标签：