#586. [FJOI2016]神秘数

[FJOI2016]神秘数

No testdata at current.

[FJOI2016]神秘数

题目描述

一个可重复数字集合 SS 的神秘数定义为最小的不能被 SS 的子集的和表示的正整数。例如 S={1,1,1,4,13}S=\{1,1,1,4,13\},有:1=11 = 12=1+12 = 1+13=1+1+13 = 1+1+14=44 = 45=4+15 = 4+16=4+1+16 = 4+1+17=4+1+1+17 = 4+1+1+1

88 无法表示为集合 SS 的子集的和,故集合 SS 的神秘数为 88

现给定长度为 nn正整数序列 aamm 次询问,每次询问包含两个参数 l,rl,r,你需要求出由 al,al+1,,ara_l,a_{l+1},\cdots,a_r 所组成的可重集合的神秘数。

输入格式

第一行一个整数 nn,表示数字个数。

第二行 nn 个正整数,从 11 编号。

第三行一个整数 mm,表示询问个数。

输出格式

对于每个询问,输出一行对应的答案。

样例 #1

样例输入 #1

5
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5

样例输出 #1

2
4
8
8
8

提示

对于 100%100\% 的数据点,1n,m1051\le n,m\le {10}^5a109\sum a\le {10}^9