{"raw_statement":[{"iden":"problem statement","content":"You are given a length-$N$ sequence $A = (A_1, \\ldots, A_N)$ of non-negative integers. Answer $Q$ queries.\nIn the $i$\\-th query, you are given integers $L_i$ and $R_i$ such that $1 \\leq L_i \\leq R_i \\leq N$. Solve the following problem for the subsequence $B = (A_{L_i}, \\ldots, A_{R_i})$ of length $R_i - L_i + 1$.\n\n> We repeat the following operation on $B$:\n> \n> *   Choose integers $i$ and $j$ with $1 \\leq i, j \\leq |B|$ such that $B_i \\ge 1$, $B_j \\ge 1$, and $1 \\leq j - i \\leq 2$. Subtract $1$ from $B_i$ and $B_j$.\n> \n> Find the maximum number of times the operation can be performed."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 200000$\n*   $1 \\leq Q \\leq 200000$\n*   $0 \\leq A_i \\leq 10^9$\n*   $1 \\leq L_i \\leq R_i \\leq N$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $Q$\n$A_1$ $\\cdots$ $A_N$\n$L_1$ $R_1$\n$\\vdots$\n$L_Q$ $R_Q$"},{"iden":"sample input 1","content":"6 1\n1 1 4 0 3 2\n1 6"},{"iden":"sample output 1","content":"5\n\nIn this example, we solve the problem for $B = (1,1,4,0,3,2)$. We can perform five operations as follows:\n\n*   Choose $i=1$ and $j=3$. Then $B = (0,1,3,0,3,2)$.\n*   Choose $i=2$ and $j=3$. Then $B = (0,0,2,0,3,2)$.\n*   Choose $i=3$ and $j=5$. Then $B = (0,0,1,0,2,2)$.\n*   Choose $i=5$ and $j=6$. Then $B = (0,0,1,0,1,1)$.\n*   Choose $i=5$ and $j=6$. Then $B = (0,0,1,0,0,0)$."},{"iden":"sample input 2","content":"6 6\n49 83 10 77 21 62\n1 1\n1 2\n1 3\n3 5\n1 6\n5 6"},{"iden":"sample output 2","content":"0\n49\n59\n31\n151\n21"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}