[Fjoi 2016]神秘数

题目描述

一个可重复数字集合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]..a[n]，m个询问，每次询问给定一个区间[l,r](l<=r)，求由a[l],a[l+1],…,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

---

提示

对于100%的数据点，n,m <= 100000，∑a[i] <= 10^9

---

题目来源

鸣谢yyh上传