配点: 100 点
葵是 您有 N 卡,这些卡包括 它们的编号最大为 1 到 N 。每张卡都有 1 正整数写在卡上。 i (1 \leqq i \leqq N中写入的整数是 A_i 。
葵使用卡片和黑板 播放 Q 次。j 回目 (1 \leqq j \leqq Q) 上执行的播放如下。
- 黑板上 0 。
- 桌子上的卡片 按从左到右的顺序排列 L_j, L_j + 1, \dots, R_j 。
- 采取以下措施
执行 R_j - L_j + 1 次。k 回目 (1 \leqq k \leqq R_j - L_j + 1) 的行为如下。
- 当前黑板上写的整数 x 从左边开始,桌子上排列着一排卡片。 k 卡上写的整数是 从黑板上擦掉 y 。x ,x + y 或 上面写着字符 x - y 。 如果您在黑板上写下x - y ,您将收到Uiro(日本甜点)。 吃 1 块。 您不能在黑板上写出小于
- 但是,0 的整数。
您想知道葵在每场比赛中最多可能吃掉多少个 Uiro。
给定卡片和游戏信息,编写一个程序来找出 Aoi 在每次游戏中吃掉的最大可能数量的 Uiro。
入力
输入是按以下格式从标准输入给出的。
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 \leqq j \leqq Q)有j 输出 Aoi 在第一次游戏中吃掉的 Uiro 的最大可能数量。
制約
- 1 \leqq N \leqq 200\,000.
- 1 \leqq A_i \leqq 100 (1 \leqq i \leqq N).
- 1 \leqq Q \leqq 200\,000.
- 1 \leqq L_j \leqq R_j \leqq N (1 \leqq j \leqq Q).
- 所有输入值都是整数。
小課題
- (3 点) N \leqq 20,Q \leqq 20.
- (5 点) N \leqq 300,Q \leqq 20.
- (7 点) N \leqq 5\,000,Q \leqq 20.
- (15 点) Q \leqq 20.
- (21 点) A_i \leqq 2 (1 \leqq i \leqq N).
- (29 点) A_i \leqq 20 (1 \leqq i \leqq N).
- (20 点)没有额外的限制。
入力例 1
5 3 4 7 2 8 2 1 3 4 4
出力例 1
1 0
1 在第二次比赛中,可能出现以下情况。
- 首先,在黑板上。 0 。
- 接下来,将卡片放在桌子上。 1, 2, 3 。
- 当前黑板上写的整数是 0 从桌子上排列的一排卡片的左边开始, 第 1 张卡上写入的整数是 在黑板上写下 3 。0 ,3 。 如果您在黑板上写下
- 当前黑板上写的整数是 3 从桌子上排列的一排卡片的左边开始, 第 2 张卡上写入的整数是 在黑板上写下 4 。3 ,7 。 如果您在黑板上写下
- 当前黑板上写的整数是 7 从桌子上排列的一排卡片的左边开始, 第 3 张卡上写入的整数是 在黑板上写下 7 。7 ,0 。尾尾 1 块。 您不能在黑板上写出小于
此时,1 葵在第一场比赛中吃掉的外郎数量是 可以证明不超过 1 件。1 葵在第一场比赛中吃掉的外郎数量是 可以证明不超过 2 。因此, 安排1 。 您将获得
2 在第二次比赛中,可能出现以下情况。
- 首先,在黑板上。 0 。
- 接下来,将卡片放在桌子上。 4 。
- 当前黑板上写的整数是 0 从桌子上排列的一排卡片的左边开始, 第 1 张卡上写入的整数是 在黑板上写下 2 。0 ,2 。 如果您在黑板上写下
此时,2 葵在第一场比赛中吃掉的外郎数量是 可以证明不超过 0 件。2 葵在第一场比赛中吃掉的外郎数量是 可以证明不超过 1 。因此, 安排0 。 您将获得
此输入示例是一个小作业。 1,2,3,4,6,7 满足约束。
入力例 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
1 在第二次比赛中,可能出现以下情况。
- 首先,在黑板上。 0 。
- 接下来,将卡片放在桌子上。 1, 2 。
- 当前黑板上写的整数是 0 从桌子上排列的一排卡片的左边开始, 第 1 张卡上写入的整数是 在黑板上写下 1 。0 ,1 。 如果您在黑板上写下
- 当前黑板上写的整数是 1 从桌子上排列的一排卡片的左边开始, 第 2 张卡上写入的整数是 在黑板上写下 2 。1 ,3 。 如果您在黑板上写下
此时,1 葵在第一场比赛中吃掉的外郎数量是 可以证明不超过 0 件。1 葵在第一场比赛中吃掉的外郎数量是 可以证明不超过 1 。因此, 安排0 。 您将获得
此输入示例满足所有子任务约束。
入力例 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
此输入示例是一个小作业。 1,2,3,4,7 满足约束。