分数: 1100 点
问题陈述
给你一个长度-N 序列 A = (A_1, \ldots, A_N) 非负整数。回答 Q 查询。
在 i-th 查询,您得到整数 L_i 和 R_i 这样 1 \leq L_i \leq R_i \leq N。解决以下问题的子序列 B = (A_{L_i}, \ldots, A_{R_i}) 长度 R_i - L_i + 1.
我们重复以下操作 B:
- 选择整数 i 和 j 与 1 \leq i, j \leq |B| 这样 B_i \ge 1, B_j \ge 1,和 1 \leq j - i \leq 2。减去 1 来自 B_i 和 B_j.
查找该操作可以执行的最大次数。
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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}).
样本输入 1
6 1 1 1 4 0 3 2 1 6
示例输出 1
5
在此示例中,我们解决了以下问题: B = (1,1,4,0,3,2)。我们可以执行以下五种操作:
- 选择 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).
示例输入 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