葵有 $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

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

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$ 的限制。

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$。
2. 将卡片 $1$, $2$ 按此顺序从左到右排列在桌面上。
3. 黑板上当前的数是 $0$，桌面左起第 $1$ 张卡片上的数是 $1$。擦去黑板上的 $0$，改为写下 $1$。
4. 黑板上当前的数是 $1$，桌面左起第 $2$ 张卡片上的数是 $2$。擦去黑板上的 $1$，改为写下 $3$。

此时，第一个游戏中葵吃掉的外郎糕数量为 $0$。可以证明第一个游戏中葵吃掉的外郎糕数量不会超过 $0$。因此，应输出 $0$。

该样例满足所有子任务的限制。

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