← 返回题目列表

AtCoder · joigsp2025_k

K. 外郎

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

配点: 100 点

葵是 您有 N 卡,这些卡包括 它们的编号最大为 1 当编号达到 N 。每张卡都有 1 正整数写在卡上。 i (1 \leqq i \leqq N中写入的整数是 A_i 。

葵使用卡片和黑板。 播放 Q 次。j 回目 (1 \leqq j \leqq Q) 上执行的播放如下。

  • 黑板上 写入 0 。
  • 桌子上的卡片 L_j, L_j + 1, \dots, R_j 。
  • 采取以下措施 执行 R_j - L_j + 1 次。k 回目 (1 \leqq k \leqq R_j - L_j + 1) 的行为如下。
    • 当前黑板上写的整数 x 桌子上排列的一排卡片从左边开始。 k 卡上写的整数是 y 。x , 在黑板上写下x + y 或 x - y 。 如果您在黑板上写下x - y ,您将收到Uiro(日本甜点)。 1 吃。
    • 但是, 您不能在黑板上写出小于0 的整数。

你想知道葵在每场比赛中吃掉的外郎的最大数量。

给定卡片和游戏信息,编写一个程序来找出 Aoi 在每次游戏中吃掉的最大可能数量的 Uiro。


入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N
Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

出力

到标准输出 Q 行。j 行目 (1 \leqq j \leqq Q)有 代表第j 输出葵在第一次游戏中吃掉的最大可能数量的 Uiro。

制約

  • 1 \leqq N \leqq 200\,000.
  • 1 \leqq A_i \leqq 100 (1 \leqq i \leqq N).
  • 1 \leqq Q \leqq 200\,000.
  • 1 \leqq L_j \leqq R_j \leqq N (1 \leqq j \leqq Q).
  • 所有输入值均为整数。

小課題

  1. (7 点) N \leqq 20,Q \leqq 20.
  2. (11 点) N \leqq 300,Q \leqq 20.
  3. (15 点) N \leqq 5\,000,Q \leqq 20.
  4. (24 点) Q \leqq 20.
  5. (21 点) A_i \leqq 2 (1 \leqq i \leqq N).
  6. (14 点) A_i \leqq 20 (1 \leqq i \leqq N).
  7. (8 点)没有额外的限制。

入力例 1

5
3 4 7 2 8
2
1 3
4 4

出力例 1

1
0

1 在第二次比赛中,可能出现以下情况。

  • 首先,在黑板上。 0 。
  • 接下来,将卡片放在桌子上。 1, 2, 3 。
  • 当前黑板上写的整数是 0 从桌子上排列的一排卡片的左侧开始, 第 1 张卡上写入的整数是 在黑板上写下 3 。0 , 在黑板上写下3 。 如果您在黑板上写下
  • 当前黑板上写的整数是 3 从桌子上排列的一排卡片的左侧开始, 第 2 张卡上写入的整数是 在黑板上写下 4 。3 , 在黑板上写下7 。 如果您在黑板上写下
  • 当前黑板上写的整数是 7 从桌子上排列的一排卡片的左侧开始, 第 3 张卡上写入的整数是 在黑板上写下 7 。7 , 在黑板上写下0 。尾尾 1 吃。

此时, 随着1 葵第一次玩时吃掉的外郎数量是 1 。 可以证明不超过1 葵第一次玩时吃掉的外郎数量是 2 。因此, 安排1 。

2 在第二次比赛中,可能出现以下情况。

  • 首先,在黑板上。 0 。
  • 接下来,将卡片放在桌子上。 4 。
  • 当前黑板上写的整数是 0 从桌子上排列的一排卡片的左侧开始, 第 1 张卡上写入的整数是 在黑板上写下 2 。0 , 在黑板上写下2 。 如果您在黑板上写下

此时, 随着2 葵第一次玩时吃掉的外郎数量是 0 。 可以证明不超过2 葵第一次玩时吃掉的外郎数量是 1 。因此, 安排0 。

此输入示例是一个小作业。 1,2,3,4,6,7 满足约束。


入力例 2

14
1 2 2 1 2 1 1 2 1 2 2 1 1 1
5
1 2
1 14
5 11
3 12
4 7

出力例 2

0
8
4
6
2

1 在第二次比赛中,可能出现以下情况。

  • 首先,在黑板上。 0 。
  • 接下来,将卡片放在桌子上。 1, 2 。
  • 当前黑板上写的整数是 0 从桌子上排列的一排卡片的左侧开始, 第 1 张卡上写入的整数是 在黑板上写下 1 。0 , 在黑板上写下1 。 如果您在黑板上写下
  • 当前黑板上写的整数是 1 从桌子上排列的一排卡片的左侧开始, 第 2 张卡上写入的整数是 在黑板上写下 2 。1 , 在黑板上写下3 。 如果您在黑板上写下

此时, 随着1 葵第一次玩时吃掉的外郎数量是 0 。 可以证明不超过1 葵第一次玩时吃掉的外郎数量是 1 。因此, 安排0 。

此输入示例满足所有子任务约束。


入力例 3

8
16 23 45 76 43 97 12 43
7
1 8
3 7
2 7
4 5
5 8
2 6
3 5

出力例 3

3
2
2
1
2
2
1

此输入示例是一个小作业。 1,2,3,4,7 满足约束。