#5055. 「JOISC 2025 Day4」外郎饼

题目译自 JOISC 2025 Day4 T3 「ういろう / Uiro」

题目描述

葵手中有 $N$ 张卡片，编号从 $1$ 到 $N$，每张卡片上写着一个正整数，卡片 $i$ ($1 \leq i \leq N$) 上的数字是 $A_i$。

她打算用这些卡片和一块黑板玩 $Q$ 次游戏。第 $j$ ($1 \leq j \leq Q$) 次游戏的规则如下：

1. 在黑板上写下 $0$。
2. 将卡片 $L_j, L_j+1, \ldots, R_j$ 按顺序从左到右排在桌上。
3. 重复以下操作 $R_j - L_j + 1$ 次，第 $k$ ($1 \leq k \leq R_j - L_j + 1$) 次操作如下：
   • 设黑板当前数字为 $x$，桌上从左第 $k$ 张卡片的数字为 $y$。
   • 擦掉 $x$，写上 $x + y$ 或 $x - y$。
   • 若写 $x - y$，葵吃一块外郎饼（一种和菓子）。
   • 注意：黑板数字不能小于 $0$。

你想知道每次游戏中葵最多能吃多少块外郎饼。给定卡片和游戏信息，编写程序计算答案。

输入格式

第一行包含一个整数 $N$。

第二行包含用空格分隔的 $N$ 个整数 $A_1, A_2, \ldots ,A_N$。

第三行包含一个整数 $Q$。

接下来的 $Q$ 行，每行包含两个整数 $L_i,R_i$。

输出格式

输出 $Q$ 行，第 $j$ ($1 \leq j \leq Q$) 行为第 $j$ 次游戏中葵最多能吃的外郎饼数。

样例 1

输入

5
3 4 7 2 8
2
1 3
4 4

输出

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$ 次游戏中葵无法吃到 $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

输出

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
2
2
1
2
2
1

这个样例满足子任务 $1,2,3,4,7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 200000$
• $1 \leq A_i \leq 100$ ($1 \leq i \leq N$)
• $1 \leq Q \leq 200000$
• $1 \leq L_j \leq R_j \leq N$ ($1 \leq j \leq Q$)
• 所有输入为整数

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	3	$N \leq 20$, $Q \leq 20$
2	5	$N \leq 300$, $Q \leq 20$
3	7	$N \leq 5000$, $Q \leq 20$
4	15	$Q \leq 20$
5	21	$A_i \leq 2$ ($1 \leq i \leq N$)
6	29	$A_i \leq 20$ ($1 \leq i \leq N$)
7	20	无附加限制