Description：

定义集合的神秘数为这个集合的子集和所不能表示出的最小正整数，给一个序列，每次询问一段区间的神秘数。

$1\leqslant n\leqslant 10^5$

Solution：

假设现在 $[1,x]$ 的所有数字都已经能求出，那么如果有一个还没有考虑过的数字 $y\leqslant x+1$ ，那么 $[1,x+y]$ 都是可以表示出的，如果所有 $y$ 都大于 $x+1$ ，那么 $x+1$ 就是神秘数。

如何快速实现这个算法呢？可以查一下所有 $\leqslant x+1$ 的数的和 $S$ ，如果 $=x$ ，那么所有 $\leqslant x+1$ 的数字都已经被考虑完了，那么 $x+1$ 就是答案，否则存在没有用过的 $y\leqslant x+1$ ， $x$ 可以更新为 $S$ 。

这样做看上去很暴力，但是每次 $x$ 至少翻倍，所以是 $O(n\log n\log 10^9)$ 的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar(); 

	}

	return res * f;

}

int n,m;

#define MAXN 100010

int a[MAXN];

#define NEG 1

#define INF 1000000000

typedef long long ll; 

struct node

{

	int lc,rc;

	ll sum;

}t[MAXN * 50];

int ptr = 0;

int newnode(){return ++ptr;}

int root[MAXN];

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	return;

}

void insert(int &rt,int p,int l,int r)

{

	int k = newnode();t[k] = t[rt];rt = k;

	if(l == r){t[rt].sum += p;return;}

	if(p <= mid)insert(t[rt].lc,p,l,mid);

	else insert(t[rt].rc,p,mid + 1,r);

	t[rt].sum = t[t[rt].lc].sum + t[t[rt].rc].sum;

	return;

}

ll query(int rtr,int rtl,int L,int R,int l,int r)

{

	if(rtl == 0 && rtr == 0)return 0;

	if(L <= l && r <= R)

	{

		if(rtl == 0)return t[rtr].sum;

		else return t[rtr].sum - t[rtl].sum;

	}

	ll res = 0;

	if(L <= mid)res += query(t[rtr].lc,t[rtl].lc,L,R,l,mid);

	if(R > mid)res += query(t[rtr].rc,t[rtl].rc,L,R,mid + 1,r);

	return res;

}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)a[i] = read();

	build(root[0],NEG,INF);

	for(int i = 1;i <= n;++i)insert((root[i] = root[i - 1]),a[i],NEG,INF);

	scanf("%d",&m);

	int l,r;

	for(int i = 1;i <= m;++i)

	{

		l = read();r = read();

		ll x = 0;

		while(true)

		{

			ll sum = query(root[r],root[l - 1],1,x + 1,NEG,INF);

			if(sum <= x)break;

			x = sum;

		}

		printf("%lld\n",x + 1);

	}

	return 0;

}