题目描述

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

Aoi 将使用这些卡片和一块黑板进行 $Q$ 次游戏。第 $j$ 次游戏 ($1 \le j \le Q$) 包含以下步骤：

1. 在黑板上写下 $0$。
2. 将卡片 $L_j, L_j + 1, \dots, R_j$ 按此顺序从左到右排列在桌面上。
3. 执行以下操作 $R_j - L_j + 1$ 次。第 $k$ 次操作 ($1 \le k \le R_j - L_j + 1$) 如下：
   • 令 $x$ 为当前写在黑板上的整数，令 $y$ 为桌面上从左往右数第 $k$ 张卡片上写的整数。擦掉黑板上的 $x$，改写为 $x + y$ 或 $x - y$。
   • 如果选择了 $x - y$，Aoi 会吃掉一块外郎糕（一种传统的日本甜点）。
   • 但是，不允许写出严格小于 $0$ 的整数。

对于每场游戏，你都需要求出 Aoi 最多能吃掉多少块外郎糕。

给定关于卡片和游戏的信息，编写一个程序，计算每场游戏中 Aoi 最多能吃掉的外郎糕数量。

输入格式

从标准输入读取以下数据：

$N$ $A_1 \ A_2 \ \dots \ A_N$ $Q$ $L_1 \ R_1$ $L_2 \ R_2$ $\vdots$ $L_Q \ R_Q$

输出格式

输出 $Q$ 行到标准输出。第 $j$ 行 ($1 \le j \le Q$) 输出 Aoi 在第 $j$ 次游戏中最多能吃掉的外郎糕数量。

数据范围

• $1 \le N \le 200\,000$。
• $1 \le A_i \le 100$ ($1 \le i \le N$)。
• $1 \le Q \le 200\,000$。
• $1 \le L_j \le R_j \le N$ ($1 \le j \le Q$)。
• 给定值均为整数。

子任务

1. (3 分) $N \le 20, Q \le 20$。
2. (5 分) $N \le 300, Q \le 20$。
3. (7 分) $N \le 5\,000, Q \le 20$。
4. (15 分) $Q \le 20$。
5. (21 分) $A_i \le 2$ ($1 \le i \le N$)。
6. (29 分) $A_i \le 20$ ($1 \le i \le N$)。
7. (20 分) 无附加限制。

样例

样例输入 1

5
3 4 7 2 8
2
1 3
4 4

样例输出 1

1
0

样例输入 2

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

样例输出 2

0
8
4
6
2

样例输入 3

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

3
2
2
1
2
2
1