题解：有一个暴力是将r-l+1个数排序之后从小到大加，设已经加的数的和为s，当前要加ai，如果s<ai-1则不能加s（然而这个我在考场上面都没想到）于是正解就是优化一下，考虑每次加数把可以加的都加进来，于是s每次扩大一倍，至于加哪些数可以用主席树，复杂度为n log^2 n。

#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100050
#define M 1073741824
int gf[N],st=0,s[N*50],c[N*50][2],v[N],n,m;
inline int Read()
 {
 	int x=0;char y;
 	do y=getchar(); while (y<'0'||y>'9');
 	do x=x*10+y-'0',y=getchar(); while (y>='0'&&y<='9');
 	return x;
 }
int Set_up(int x,int y,int z,int o)
 {
 	int i=x + y >> 1,j=++st;
 	if (x==y) {s[j]=s[z]+o;return j;}
    if (o<=i) c[j][1]=c[z][1],c[j][0]=Set_up(x,i,c[z][0],o);else
 	  c[j][0]=c[z][0],c[j][1]=Set_up(i+1,y,c[z][1],o);
 	s[j]=s[c[j][0]]+s[c[j][1]];
 	return j;
 }
int Find(int x,int y,int z,int o,int p,int u)
 {
 	int i=x + y >> 1,j=0;
 	if (x==p&&y==u) return s[o]-s[z];
 	if (p<=i) j=Find(x,i,c[z][0],c[o][0],p,min(u,i));
 	if (u>i) j+=Find(i+1,y,c[z][1],c[o][1],max(p,i+1),u);
 	return j;
 }
int Solve(int y,int x)
 {
 	int k=0,l=0,q=0;
 	do
 	 {
 	 	l=Find(0,M-1,gf[x-1],gf[y],q+1,k+1);
 	 	if (!l) return k+1;
 	 	q=k+1;k=k+l;
 	 } while (1);
 }
int main()
 {
 	freopen("hhsum.in","r",stdin);
 	freopen("hhsum.out","w",stdout);
 	n=Read();
 	for (int i=1;i<=n;i++) v[i]=Read();
 	for (int i=1;i<=n;i++)
 	  gf[i]=Set_up(0,M-1,gf[i-1],v[i]);
 	m=Read();
 	while (m--)
 	  printf("%d\n",Solve(Read(),Read()));
 	return 0;
 }