{"raw_statement":[{"iden":"problem statement","content":"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.\nTakahashi, 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:\n\n*   Set an integer $x$ $(l \\leq x \\leq r-1)$ and increase the heights of Buildings $x$ and $x+1$ by $1$ each.\n*   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.\n\nNote that the range of $x$ depends on $(l,r)$.\nHow many choices of $(l, r)$ are there where Takahashi can realize his plan?"},{"iden":"constraints","content":"*   $2 \\leq N \\leq 300000$\n*   $1 \\leq A_i \\leq 10^9$ $(1 \\leq i \\leq N)$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"5\n5 8 8 6 6"},{"iden":"sample output 1","content":"3\n\nTakahashi can realize his plan for $(l, r) = (2, 3), (4, 5), (2, 5)$.\nFor example, for $(l, r) = (2, 5)$, the following sequence of operations make the heights of Buildings $2, 3, 4, 5$ all zero.\n\n*   Decrease the heights of Buildings $4$ and $5$ by $1$ each, six times in a row.\n*   Decrease the heights of Buildings $2$ and $3$ by $1$ each, eight times in a row.\n\nFor the remaining seven choices of $(l, r)$, there is no sequence of operations that can realize his plan."},{"iden":"sample input 2","content":"7\n12 8 11 3 3 13 2"},{"iden":"sample output 2","content":"3\n\nTakahashi can realize his plan for $(l, r) = (2, 4), (3, 7), (4, 5)$.\nFor example, for $(l, r) = (3, 7)$, the following figure shows one possible solution.\n![image](https://img.atcoder.jp/arc119/392b686a479008a3dbc3fb36893ed144.png)"},{"iden":"sample input 3","content":"10\n8 6 3 9 5 4 7 2 1 10"},{"iden":"sample output 3","content":"1\n\nTakahashi can realize his plan for $(l, r) = (3, 8)$ only."},{"iden":"sample input 4","content":"14\n630551244 683685976 249199599 863395255 667330388 617766025 564631293 614195656 944865979 277535591 390222868 527065404 136842536 971731491"},{"iden":"sample output 4","content":"8"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}