AT_arc190_e [ARC190E] Gaps of 1 or 2

長さ $ N $ の非負整数列 $ A=(A_1,\ldots,A_N) $ が与えられます． $ Q $ 個のクエリに答えてください． $ i $ 番目のクエリでは $ 1\leq L_i\leq R_i\leq N $ を満たす整数 $ L_i, R_i $ が与えられるので，長さ $ R_i-L_i+1 $ の列 $ B=(A_{L_i},\ldots,A_{R_i}) $ に対して次の問題を解いてください． > $ B $ に対して次の操作を繰り返すことを考えます． > > - $ 1\leq i,j\leq |B| $ を満たす整数 $ i,j $ であって， $ 1\leq B_i,B_j $ かつ $ 1\leq j-i\leq 2 $ を満たすものを選ぶ． $ B_i, B_j $ から $ 1 $ を引く． > > 操作を行う回数としてありうる最大値を求めてください．

入力は以下の形式で標準入力から与えられます． > $ N $ $ Q $ $ A_1 $ $ \cdots $ $ A_N $ $ L_1 $ $ R_1 $ $ \vdots $ $ L_Q $ $ R_Q $

$ Q $ 行出力してください． $ i $ 行目には $ B=(A_{L_i},\ldots,A_{R_i}) $ に操作を行う回数としてありうる最大値を出力してください．

### Sample Explanation 1 この例では $ B=(1,1,4,0,3,2) $ に対して問題を解くことになります．次のようにして $ 5 $ 回の操作を行うことができます． - $ i=1,j=3 $ として操作を行う． $ B=(0,1,3,0,3,2) $ になる． - $ i=2,j=3 $ として操作を行う． $ B=(0,0,2,0,3,2) $ になる． - $ i=3,j=5 $ として操作を行う． $ B=(0,0,1,0,2,2) $ になる． - $ i=5,j=6 $ として操作を行う． $ B=(0,0,1,0,1,1) $ になる． - $ i=5,j=6 $ として操作を行う． $ B=(0,0,1,0,0,0) $ になる． ### Constraints - $ 1\leq N\leq 200000 $ - $ 1\leq Q\leq 200000 $ - $ 0\leq A_i\leq 10^9 $ - $ 1\leq L_i\leq R_i\leq N $ - 入力される値はすべて整数である