#include <stdio.h>
#include <algorithm>
using namespace std;
int tree[900000];
bool des[900000];
bool lij[900000];
int a,b,c,d,e,f,g,l;
bool pi=false;
bool h=false;
int pi2=0;
int query(int cvor,int from,int to,int a,int b)
{
    //if(a==0 && b==g-1){pi2=tree[1];return tree[1];}
    if(from>=a && to<=b)
    {
      //printf("%d\n",pi);
      //printf("TT %d %d. %d,%d\n",tree[cvor],cvor,lij[cvor],des[cvor]);
      if(l==0){pi=des[cvor];pi2=tree[cvor];}
      else
      {
          if(pi2<0 && tree[cvor]<0 && tree[cvor]>=pi2)
          {
                   pi2=tree[cvor];
                   pi=des[cvor];
          }
          else if(pi2>tree[cvor] && tree[cvor]<0){h=true;}
          else if(pi2<tree[cvor] && pi2<0)
          {
            pi2=tree[cvor];
            pi=des[cvor];
          }
          else if(pi && lij[cvor] && !h)pi2+=tree[cvor];
          else if(pi2>tree[cvor] && !h)
          {
               h=true;
          }
          else if(pi2<=tree[cvor] && !h)
          {
               pi2=tree[cvor];
               pi=des[cvor];
          }
          else if(h && pi2<tree[cvor])
          {
               pi2=tree[cvor];
          }
      }
      //l=max(l,tree[cvor]);
      ++l;
      return tree[cvor];
    }
    int m1=-988988,m2=-9565656;
    if((from+to)/2>=a)m1=query(cvor*2,from,(from+to)/2,a,b);
    if((from+to)/2+1<=b)m2=query(cvor*2+1,(from+to)/2+1,to,a,b);
    return max(m1,m2);
}
int main()
{
    scanf("%d",&a);
    g=a;
    for(b=1;b<a;b*=2){}
    for(int i=0;i<b+a+1;++i)tree[i]=-950000;
    for(int i=0;i<a;++i)
    {scanf("%d",&tree[i+b]);des[i+b]=true;lij[i+b]=true;}
    for(int i=b+a-1;i>1;--i)
    {
            /*if(tree[i/2]==-50000)
            {*/
               if(i%2==1)
               {
                  tree[i/2]=tree[i];
                  lij[i/2]=lij[i];
                  des[i/2]=des[i];
               }
               else if(i%2==0)
               {
                   if(tree[i/2]==-950000){tree[i/2]=tree[i];lij[i/2]=lij[i];des[i/2]=des[i];}
                   else if(tree[i/2]>=tree[i] && tree[i]<0){lij[i/2]=false;}
                   else if(tree[i/2]<0 && tree[i]>=0){tree[i/2]=tree[i];des[i/2]=false;lij[i/2]=lij[i];}
                   else if(tree[i/2]<0 && tree[i]<0 && tree[i]>=tree[i/2]){tree[i/2]=tree[i];des[i/2]=false;lij[i/2]=lij[i];}
                   else if(lij[i+1]==true && des[i]==true)
                   {
                      if(tree[i/2]+tree[i]>tree[i/2])
                     {
                       tree[i/2]+=tree[i];
                       lij[i/2]=lij[i];
                     }
                   }
                   else if(tree[i/2]<tree[i])
                   {
                      tree[i/2]=tree[i];
                      des[i/2]=false;
                      lij[i/2]=lij[i];
                   }
               }
           //printf("%d. %d --> %d  %d %d\n",i,tree[i],tree[i/2],lij[i],des[i]);
    }
    //printf("%d\n",tree[1]);
    scanf("%d",&c);
    for(int i=0;i<c;++i)
    {
            scanf("%d%d",&e,&f);
            int ioi=query(1,0,b-1,e-1,f-1);
            printf("%d\n",pi2);
            pi=false;
            h=false;
            pi2=0;
            l=0;
    }
    return 0;
}