← 返回题目列表

AtCoder · arc190_e

E. 间隙为 1 或 2

中文机器翻译题面 查看原题

分数: 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