#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
typedef int ull;
#define M 100000
ull maxans;
ull arr[M];
ull constructF(ull ss,ull se,ull *st,ull si)
{
if(ss==se)
{
st[si]=arr[ss];
return st[si];
}
ull mid=(se+ss)/2;
st[si]=constructF(ss,mid,st,2*si+1)+constructF(mid+1,se,st,2*si+2);
return st[si];
}
ull *construct(ull n)
{
ull x=(ceil(log2(n)));
ull max_size=2*pow(2,x)-1;
ull *st=new ull[max_size];
constructF(0,n-1,st,0);
/*for(int i=0; i<max_size;i++)
{
cout<<*(st+i)<<" ";
}*/
return st;
}
ull getSumF(ull *st,ull ss,ull se,ull qs,ull qe,ull index)
{
if(ss>=qs&&se<=qe)
{
if(maxans<st[index])
maxans=st[index];
if(ss!=se)
{
ull mid=(ss+se)/2;
getSumF(st,ss,mid,qs,qe,2*index+1);
getSumF(st,mid+1,se,qs,qe,2*index+2);
}
return st[index];
}
if(se<qs||ss>qe)
{
return 0;
}
ull mid = (se+ss)/2;
ull val=getSumF(st,ss,mid,qs,qe,2*index+1)+getSumF(st,mid+1,se,qs,qe,2*mid+2);
if(maxans<val)
maxans=val;
return val;
}
/*ull getSum(ull arr[],ull *st,ull n,ull qs,ull qe)
{
if(qs<0||qe>n-1||qs>qe)
return 0;
}*/
int main()
{
ull n;
scanf("%d",&n);
for(ull i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
ull m;
scanf("%d",&m);
ull *st=construct(n);
while(m--)
{
ull x,y;
maxans=-10000;
scanf("%d%d",&x,&y);
//getSum(arr,st,n,x-1,y-1);
getSumF(st,0,n-1,x-1,y-1,0);
printf("%d\n",maxans);
}
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHN0ZGlvLmg+CiNpbmNsdWRlPG1hdGguaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAp0eXBlZGVmIGludCB1bGw7CiAKI2RlZmluZSBNIDEwMDAwMAp1bGwgbWF4YW5zOwp1bGwgYXJyW01dOwp1bGwgY29uc3RydWN0Rih1bGwgc3MsdWxsIHNlLHVsbCAqc3QsdWxsIHNpKQp7CmlmKHNzPT1zZSkKewpzdFtzaV09YXJyW3NzXTsKcmV0dXJuIHN0W3NpXTsKfQogCnVsbCBtaWQ9KHNlK3NzKS8yOwogCnN0W3NpXT1jb25zdHJ1Y3RGKHNzLG1pZCxzdCwyKnNpKzEpK2NvbnN0cnVjdEYobWlkKzEsc2Usc3QsMipzaSsyKTsKIApyZXR1cm4gc3Rbc2ldOwp9CiAKdWxsICpjb25zdHJ1Y3QodWxsIG4pCnsKdWxsIHg9KGNlaWwobG9nMihuKSkpOwp1bGwgbWF4X3NpemU9Mipwb3coMix4KS0xOwp1bGwgKnN0PW5ldyB1bGxbbWF4X3NpemVdOwogCmNvbnN0cnVjdEYoMCxuLTEsc3QsMCk7CiAvKmZvcihpbnQgaT0wOyBpPG1heF9zaXplO2krKykKIHsKIAljb3V0PDwqKHN0K2kpPDwiICI7CiB9Ki8KcmV0dXJuIHN0Owp9CiAKdWxsIGdldFN1bUYodWxsICpzdCx1bGwgc3MsdWxsIHNlLHVsbCBxcyx1bGwgcWUsdWxsIGluZGV4KQp7CmlmKHNzPj1xcyYmc2U8PXFlKQp7CmlmKG1heGFuczxzdFtpbmRleF0pCm1heGFucz1zdFtpbmRleF07CmlmKHNzIT1zZSkKewp1bGwgbWlkPShzcytzZSkvMjsKZ2V0U3VtRihzdCxzcyxtaWQscXMscWUsMippbmRleCsxKTsKZ2V0U3VtRihzdCxtaWQrMSxzZSxxcyxxZSwyKmluZGV4KzIpOwp9CnJldHVybiBzdFtpbmRleF07Cn0KIAppZihzZTxxc3x8c3M+cWUpCnsKcmV0dXJuIDA7Cn0KdWxsIG1pZCA9IChzZStzcykvMjsKdWxsIHZhbD1nZXRTdW1GKHN0LHNzLG1pZCxxcyxxZSwyKmluZGV4KzEpK2dldFN1bUYoc3QsbWlkKzEsc2UscXMscWUsMiptaWQrMik7CmlmKG1heGFuczx2YWwpCm1heGFucz12YWw7CiAKcmV0dXJuIHZhbDsKfQovKnVsbCBnZXRTdW0odWxsIGFycltdLHVsbCAqc3QsdWxsIG4sdWxsIHFzLHVsbCBxZSkKewogIGlmKHFzPDB8fHFlPm4tMXx8cXM+cWUpCiAgcmV0dXJuIDA7CiAKIAp9Ki8KaW50IG1haW4oKQp7CnVsbCBuOwpzY2FuZigiJWQiLCZuKTsKIApmb3IodWxsIGk9MDtpPG47aSsrKQp7CnNjYW5mKCIlZCIsJmFycltpXSk7Cn0KdWxsIG07CnNjYW5mKCIlZCIsJm0pOwp1bGwgKnN0PWNvbnN0cnVjdChuKTsKCndoaWxlKG0tLSkKewp1bGwgeCx5OwptYXhhbnM9LTEwMDAwOwpzY2FuZigiJWQlZCIsJngsJnkpOwovL2dldFN1bShhcnIsc3Qsbix4LTEseS0xKTsKZ2V0U3VtRihzdCwwLG4tMSx4LTEseS0xLDApOwpwcmludGYoIiVkXG4iLG1heGFucyk7Cn0KcmV0dXJuIDA7Cn0=