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.