Description
一个可重复数字集合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]所构成的可重复数字集合的神秘数。
Input
第一行一个整数n，表示数字个数。
第二行n个整数，从1编号。
第三行一个整数m，表示询问个数。
以下m行，每行一对整数l,r，表示一个询问。
Output
对于每个询问，输出一行对应的答案。
Sample Input
5
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5
1 2 4 9 10
5
1 1
1 2
1 3
1 4
1 5
Sample Output
2
4
8
8
8
4
8
8
8
HINT
对于100%的数据点，n,m <= 100000，∑a[i] <= 10^9
我们先来考虑一个简单的问题，给定一个集合S，怎么求它的神秘数。
我们可以将S从小到大排序，设当前的神秘数为ans，即[1,ans-1]的所有数都能用S的子集和表示而ans不能用S的子集和表示。
那么将一个v加入S中，那么[v,ans+v-1]的所有数都可以用S表示了。
那么可以发现一个神奇的事情：
当v<=ans时，ans+=v。
当v<=ans时，ans+=v。
当v>ans时，ans不变。
那么将这个算法拓展到区间上，ans从1开始，每次计算该区间中大小在[1,ans]的数之和为v，则赋值ans=v+1。
因为ans每次至少翻一倍，最多logn次迭代。
然后用主席树来维护一下就好了。
#include<cstdio>
#include<cctype>
#include<queue>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define dwn(i,s,t) for(int i=s;i>=t;i--)
#define ren for(int i=first[x];i;i=next[i])
using namespace std;
const int BufferSize=<<;
char buffer[BufferSize],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,,BufferSize,stdin);
tail=(head=buffer)+l;
}
return *head++;
}
inline int read() {
int x=,f=;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-;
for(;isdigit(c);c=Getchar()) x=x*+c-'';
return x*f;
}
const int maxn=;
const int maxnode=;
int n,m,sum,root[maxn],A[maxn],sumv[maxnode],ls[maxnode],rs[maxnode],ToT;
void update(int& y,int x,int l,int r,int pos) {
sumv[y=++ToT]=sumv[x]+pos;
if(l==r) return;int mid=l+r>>;
ls[y]=ls[x];rs[y]=rs[x];
if(pos<=mid) update(ls[y],ls[x],l,mid,pos);
else update(rs[y],rs[x],mid+,r,pos);
}
int query(int y,int x,int l,int r,int pos) {
if(l==r) return sumv[y]-sumv[x];
int mid=l+r>>;
if(pos<=mid) return query(ls[y],ls[x],l,mid,pos);
return query(rs[y],rs[x],mid+,r,pos)+sumv[ls[y]]-sumv[ls[x]];
}
int query(int x,int y) {
int ans=;
for(int t;;ans=t+) {
if((t=query(root[y],root[x],,sum,ans))<ans) break;
}
return ans;
}
int main() {
n=read();sum=;
rep(i,,n) A[i]=read(),sum+=A[i];
rep(i,,n) update(root[i],root[i-],,sum,A[i]);
m=read();
rep(i,,m) {
int l=read(),r=read();
printf("%d\n",query(l-,r));
}
return ;
}