葵有 $N$ 张卡片，每张卡片上标有 $1$ 到 $N$ 的编号。每张卡片上写有一个正整数，对于卡片 $i$（$1 \leq i \leq N$），其上写的整数为 $A_i$。

葵将用卡片和黑板进行 $Q$ 次游戏。第 $j$ 次（$1 \leq j \leq Q$）游戏规则如下：

• 在黑板上写上 $0$。
• 将卡片 $L_j, L_j + 1, \dots, R_j$ 按顺序从左到右排成一行。
• 此后共进行 $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$，则吃掉 $1$ 个“ういろう”（日式点心）。
  • 但是，不能在黑板上写下小于 $0$ 的整数。

你需要求出，对于每次游戏，葵最多能吃多少个“ういろう”。

现在给定卡片和游戏的信息，请编写程序，计算每次游戏中葵最多能吃多少个“ういろう”。

输入以如下格式由标准输入给出：

$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 \leq j \leq Q$）输出第 $j$ 次游戏中葵最多能吃到的“ういろう”数量。

子任务

1.（7 分）$N \leq 20$，$Q \leq 20$。
2.（11 分）$N \leq 300$，$Q \leq 20$。
3.（15 分）$N \leq 5\,000$，$Q \leq 20$。
4.（24 分）$Q \leq 20$。
5.（21 分）$A_i \leq 2$（$1 \leq i \leq N$）。
6.（14 分）$A_i \leq 20$（$1 \leq i \leq N$）。
7.（8 分）无其他限制。

---

样例解释 1

第 $1$ 次游戏可能如下：

• 首先在黑板写 $0$。
• 然后将卡片 $1,2,3$ 按顺序排列。
• 当前黑板上的数为 $0$，第 $1$ 张卡片上的数为 $3$。将黑板改写为 $3$。
• 当前黑板上的数为 $3$，第 $2$ 张卡片上的数为 $4$。将黑板改写为 $7$。
• 当前黑板上的数为 $7$，第 $3$ 张卡片上的数为 $7$。将黑板改写为 $0$，并吃掉 $1$ 个ういろう。

此时，第 $1$ 次游戏最多能吃 $1$ 个ういろう，提高到 $2$ 个是不可能的。因此输出 $1$。

第 $2$ 次游戏可能如下：

• 首先在黑板写 $0$。
• 然后排列卡片 $4$。
• 当前黑板上的数为 $0$，第 $4$ 张卡片上的数为 $2$。将黑板改写为 $2$。

此时，第 $2$ 次游戏最多能吃 $0$ 个ういろう，不可能更高。因此输出 $0$。

此输入样例满足子任务 $1,2,3,4,6,7$ 的约束。

---

样例解释 2

第 $1$ 次游戏可能如下：

• 首先在黑板写 $0$。
• 然后排列卡片 $1,2$。
• 当前黑板上的数为 $0$，第 $1$ 张卡片上的数为 $1$。将黑板改写为 $1$。
• 当前黑板上的数为 $1$，第 $2$ 张卡片上的数为 $2$。将黑板改写为 $3$。

此时，第 $1$ 次游戏最多能吃 $0$ 个ういろう，不可能更高。因此输出 $0$。

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

---

样例解释 3

此输入样例满足子任务 $1,2,3,4,7$ 的约束。

数据范围

• $1 \leq N \leq 200\,000$。
• $1 \leq A_i \leq 100$（$1 \leq i \leq N$）。
• $1 \leq Q \leq 200\,000$。
• $1 \leq L_j \leq R_j \leq N$（$1 \leq j \leq Q$）。
• 输入的所有数均为整数。

由 ChatGPT 5 翻译