P11994 [JOIST 2025] 外郎糕 / 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$, ..., $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$，葵将吃掉一个外郎糕。 - 但此时写在黑板上的数必须严格非负。 对于每个游戏，你需要求出葵能吃掉外郎糕的最大数量。 给定卡片信息和游戏信息，请编写程序计算每个游戏中葵能吃掉外郎糕的最大数量。

> $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$ 解释 在**第一个游戏**中，一种可能的操作序列如下： 1. 在黑板上写下 $0$。 2. 将卡片 $1$, $2$, $3$ 按此顺序从左到右排列在桌面上。 3. 黑板上当前的数是 $0$，桌面左起第 $1$ 张卡片上的数是 $3$。擦去黑板上的 $0$，改为写下 $3$。 4. 黑板上当前的数是 $3$，桌面左起第 $2$ 张卡片上的数是 $4$。擦去黑板上的 $3$，改为写下 $7$。 5. 黑板上当前的数是 $7$，桌面左起第 $3$ 张卡片上的数是 $7$。擦去黑板上的 $7$，改为写下 $0$。葵吃掉一个外郎糕。 此时，第一个游戏中葵吃掉的外郎糕数量为 $1$。可以证明第一个游戏中葵吃掉的外郎糕数量不会超过 $1$。因此，应输出 $1$。 在**第二个游戏**中，一种可能的操作序列如下： 1. 在黑板上写下 $0$。 2. 将卡片 $4$ 排列在桌面上。 3. 黑板上当前的数是 $0$，桌面左起第 $1$ 张卡片上的数是 $2$。擦去黑板上的 $0$，改为写下 $2$。 此时，第二个游戏中葵吃掉的外郎糕数量为 $0$。可以证明第二个游戏中葵吃掉的外郎糕数量不会超过 $0$。因此，应输出 $0$。 该样例满足子任务 $1\sim 4,6,7$ 的限制。 #### 样例 $2$ 解释 在第一个游戏中，另一种可能的操作序列如下： 1. 在黑板上写下 $0$。 2. 将卡片 $1$, $2$ 按此顺序从左到右排列在桌面上。 3. 黑板上当前的数是 $0$，桌面左起第 $1$ 张卡片上的数是 $1$。擦去黑板上的 $0$，改为写下 $1$。 4. 黑板上当前的数是 $1$，桌面左起第 $2$ 张卡片上的数是 $2$。擦去黑板上的 $1$，改为写下 $3$。 此时，第一个游戏中葵吃掉的外郎糕数量为 $0$。可以证明第一个游戏中葵吃掉的外郎糕数量不会超过 $0$。因此，应输出 $0$。 该样例满足所有子任务的限制。 #### 样例 $3$ 解释 该样例满足子任务 $1\sim 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$）； - 所有给定值均为整数。 ### 子任务 - $\text{Subtask 1 (3 pts)}$：$N \leq 20$，$Q \leq 20$； - $\text{Subtask 2 (5 pts)}$：$N \leq 300$，$Q \leq 20$； - $\text{Subtask 3 (7 pts)}$：$N \leq 5\,000$，$Q \leq 20$； - $\text{Subtask 4 (15 pts)}$：$Q \leq 20$； - $\text{Subtask 5 (21 pts)}$：$A_i \leq 2$（$1 \leq i \leq N$）； - $\text{Subtask 6 (29 pts)}$：$A_i \leq 20$（$1 \leq i \leq N$）； - $\text{Subtask 7 (20 pts)}$：无额外限制。