题目描述

葵有 $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$ 个游戏中葵能吃掉外郎糕的最大数量。

5
3 4 7 2 8
2
1 3
4 4

1
0

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

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$ 解释

在第一个游戏中，一种可能的操作序列如下：

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)}$：无额外限制。