#2174. 「FJOI2016」神秘数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

一个可重复数字集合 S 的神秘数定义为最小的不能被 S 的子集的和表示的正整数。例如

S = {1,1,1,4,13}
1 = 1
2 = 1+1
3 = 1+1+1
4 = 4
5 = 4+1
6 = 4+1+1
7 = 4+1+1+1

8 无法表示为集合 S 的子集的和,故集合 S 的神秘数为 8

现给定 n 个正整数 a_1\cdots a_n m 个询问,每次询问给定一个区间 [l,r] \ (l\leq r) ,求由 a_l,a_{l+1},\ldots,a_r 所构成的可重复数字集合的神秘数。

输入格式

第一行一个整数 n ,表示数字个数。
第二行 n 个整数,从 1 编号。
第三行一个整数 m ,表示询问个数。
以下 m 行,每行一对整数 l,r ,表示一个询问。

输出格式

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

样例

样例输入

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

样例输出

2
4
8
8
8

数据范围与提示

对于 10 \% 的数据点, n,m \leq 10
对于 30 \% 的数据点, n,m \leq 1000
对于 60 \% 的数据点, n,m \leq 50000
对于 100 \% 的数据点, n,m \leq 100000 \sum a_i \leq 10^9