AT_arc190_e [ARC190E] Gaps of 1 or 2

给定一个长度为 N 的非负整数序列 $A=(A_1,…,A_N)$，需要回答 $Q$ 个查询。 对于第 $i$ 个查询，给定满足 $1≤L_i≤R_i≤N$ 的整数 $L_i$和 $ R_i$，考虑长度为 $R_i−L_i+1$ 的子序列 $B=(A_{L_i},…,A_{R_i}$)。 对于子序列 $B$，考虑重复执行以下操作： 1. 选择满足 $1≤i,j≤∣B∣$ 且 $1≤B_i,B_j$且$1≤j−i≤2$的整数 $i$ 和 $j$。 2. 从 $B_i$ 和 $B_j$ 中各减去 $1$。 求出可以执行操作的最大次数。

输入来自标准输入，格式如下： $ N \hspace{0.2cm} Q\\ A_1\hspace{0.2cm}⋯ \hspace{0.2cm}A_N\\ L_1\hspace{0.2cm}R_1\\ ⋮\\ L_Q\hspace{0.2cm}R_Q $

请输出$Q$行。 第$i$行输出对于子序列 $B=(A_{L_i},…,A_{R_i} )$ 可以执行操作的最大次数。 ### 【样例组】 #### 输入1 ``` 6 1 1 1 4 0 3 2 1 6 ``` #### 输出1 ``` 5 ``` #### 输入2 ``` 6 6 49 83 10 77 21 62 1 1 1 2 1 3 3 5 1 6 5 6 ``` #### 输出2 ``` 0 49 59 31 151 21 ``` ### 【样例解释】 在这个示例中，我们求解的问题是对于给定的序列 B=(1,1,4,0,3,2)，我们可以执行以下五项操作： 1. 选择 $i=1$ 和 $j=3$。然后，将 $B_i$ 和 $B_j$ 各减去 $1$，得到 $B=(0,1,3,0,3,2)$。 2. 选择 $i=2$ 和 $j=3$。然后，将 $B_i$ 和 $B_j$ 各减去 $1$，得到 $B=(0,0,2,0,3,2)$。 3. 选择 $i=3$ 和 $j=5$。然后，将 $B_i$ 和 $B_j$ 各减去 $1$，得到 $B=(0,0,1,0,2,2)$。 4. 选择 $i=5$ 和 $j=6$。然后，将 $B_i$ 和 $B_j$ 各减去 $1$，得到 $B=(0,0,1,0,1,1)$。 5. 选择 $i=5$ 和 $j=6$。然后，将 $B_i$ 和 $B_j$ 各减去 $1$，得到 $B=(0,0,1,0,0,0)$。 因此，可以执行操作的最大次数是5。

$ 1≤N≤200000\\ 1≤Q≤200000\\ 0≤A_i≤10^9\\ 1≤L_i≤R_i≤N\\ $ 所有输入值均为整数。