配点 : 100 点
問題文
在巴肯,有在年初展示“双麻糬”的习俗,这是一种将麻糬垂直堆叠而成的幸运符。这种双麻糬具有以下特性。
- 计算从上到下堆叠的每个麻糬的重量。 V_1, V_2, \dots, V_n(麻糬的数量是 n ),然后全部 i (1 \leq i \leq n-1)对于 2 \times V_i \leq V_{i+1} 成立。
Pakeko,Pakken 国家的居民, 我有 1 减去 N 化学品有 N 麻糬。麻糬 i (1 \leq i \leq N) 的权重是 W_i 。 在这里,所有 i (1 \leq i \leq N-1)关于 W_i \leq W_{i+1} 成立。 帕克科适合你 进行 Q 查询。 第 i 个查询是 来自号码 L_i 从回合开始 R_i 如果您使用每个数字仅使用一个麻糬来制作多个双麻糬,您会制作多少个双麻糬? ”是内容,请回答每项所需的最少数量。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq W_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)
- W_i \leq W_{i+1} (1 \leq i \leq N-1)
- 所有输入均为整数
小課題
- (1 点) N \leq 6 , Q = 1
- (4 点) N \leq 16 , Q = 1
- (10 点) N \leq 2000 , Q = 1
- (10 点) Q = 1
- (75 点)无附加约束 打印第
入力
输入是按以下格式从标准输入给出的。
N Q W_1 W_2 \ldots W_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
出力
Q 行。 i 在线 i 个查询的答案。 在第
入力例 1
7 3 2 3 3 4 6 8 16 3 7 2 2 1 7
出力例 1
2 1 3
1 次查询中,使用的每个年糕的重量为 3,4,6,8,16 。
- 重量为 使用 3 和 按字典顺序比较 6 麻糬的双麻糬
- 重量为 使用 4,8,16 麻糬的双麻糬
像这样 2 制作一份双麻糬,制作的双麻糬数量为 2 件,这是最少的。 在第
2 次查询中,使用的麻糬的重量为
仅 3 。在这种情况下,制作双麻糬的数量必须是
将会有 1 块。
麻糬 1 请注意,即使只有一个麻糬本身也被视为双麻糬。
3 次查询中,使用的每个年糕的重量为 2,3,3,4,6,8,16 。
- 重量为 使用 3 和 按字典顺序比较 6 麻糬的双麻糬
- 重量为 使用 2,4,8,16 麻糬的双麻糬
- 重量为 使用 3 由单个麻糬组成的双麻糬 通过制作
像这样 3 双麻糬,制作的双麻糬数量为 3 件,这是最少的。
在第
此示例是一个小作业。 5 约束。