葵有 $N$ 张卡片，编号从 $1$ 到 $N$。每张卡片上都写有一个正整数。卡片 $i$（$1\le i\le N$）上写的数是 $A_i$。

葵将使用这些卡片和黑板进行 $Q$ 次游戏。她进行的第 $j$ 次游戏（$1\le j\le Q$）包含以下步骤：

1. 在黑板上写下 $0$。
2. 将编号为 $L_j$, $L_j+1$, ..., $R_j$ 的卡片按此顺序从左到右排列在桌面上。
3. 进行 $R_j-L_j+1$ 次操作。第 $k$ 次操作（$1\le k\le 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$
• $⋮$
• $L_Q$ $R_Q$

输出格式

输出 $Q$ 行。第 $j$ 行（$1\le j\le Q$）输出第 $j$ 个游戏中葵能吃掉外郎糕的最大数量。

样例一

input

5  
3 4 7 2 8  
2  
1 3  
4 4

output

1  
0

explanation

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

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

样例二

input

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

output

0  
8  
4  
6  
2

explanation

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

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

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

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

样例三

input

8  
16 23 45 76 43 97 12 43  
7  
1 8  
3 7  
2 7  
4 5  
5 8  
2 6  
3 5

output

3  
2  
2  
1  
2  
2  
1

explanation

该样例满足子任务 $1\sim 4,7$ 的限制。

数据范围

• $1\le N\le 200000$；
• $1\le A_i\le 100$（$1\le i\le N$）；
• $1\le Q\le 200000$；
• $1\le L_j\le R_j\le N$（$1\le j\le Q$）；
• 所有给定值均为整数。

子任务

• $\text{Subtask 1 (3 pts)}$：$N\le 20$，$Q\le 20$；
• $\text{Subtask 2 (5 pts)}$：$N\le 300$，$Q\le 20$；
• $\text{Extra close brace or missing open brace}$：$N\le 5000$，$Q\le 20$；
• $\text{Subtask 4 (15 pts)}$：$Q\le 20$；
• $\text{Subtask 5 (21 pts)}$：$A_i\le 2$（$1\le i\le N$）；
• $\text{Subtask 6 (29 pts)}$：$A_i\le 20$（$1\le i\le N$）；
• $\text{Subtask 7 (20 pts)}$：无额外限制。