{"problem":{"name":"Gaps of 1 or 2","description":{"content":"You are given a length-$N$ sequence $A = (A_1, \\ldots, A_N)$ of non-negative integers. Answer $Q$ queries. In the $i$\\-th query, you are given integers $L_i$ and $R_i$ such that $1 \\leq L_i \\leq R_i \\","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc190_e"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc190_e","tags":[],"sample_group":[["6 1\n1 1 4 0 3 2\n1 6","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)$."],["6 6\n49 83 10 77 21 62\n1 1\n1 2\n1 3\n3 5\n1 6\n5 6","0\n49\n59\n31\n151\n21"]],"created_at":"2026-03-03 11:01:13"}}