Description

Input:

3

-1 2 3

1

1 2

Output:

2

Hint

 /*by SilverN*/

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #define lc rt<<1

 #define rc rt<<1|1

 using namespace std;

 const int mxn=;

 int read(){

     int x=,f=;char ch=getchar();

     while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m;

 int data[mxn];

 struct node{

     int mx;

     int ml,mr;

     int smm;

 }t[mxn<<],tmp0;

 void Build(int l,int r,int rt){

     if(l==r){t[rt].mx=t[rt].ml=t[rt].mr=data[l];t[rt].smm=data[l];return;}

     int mid=(l+r)>>;

     Build(l,mid,lc);

     Build(mid+,r,rc);

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

     t[rt].mx=max(t[lc].mx,t[rc].mx);

     t[rt].mx=max(t[lc].mr+t[rc].ml,t[rt].mx);

     t[rt].ml=max(t[lc].ml,t[lc].smm+t[rc].ml);

     t[rt].mr=max(t[rc].mr,t[rc].smm+t[lc].mr);

     return;

 }

 node query(int L,int R,int l,int r,int rt){

 //    printf("%d %d %d %d %d\n",L,R,l,r,rt);

     if(L<=l && r<=R){return t[rt];}

     int mid=(l+r)>>;

     node res1;

     if(L<=mid)res1=query(L,R,l,mid,lc);

         else res1=tmp0;

     node res2;

     if(R>mid)res2=query(L,R,mid+,r,rc);

         else res2=tmp0;

     node res={};

     res.smm=res1.smm+res2.smm;

     res.mx=max(res1.mx,res2.mx);

     res.mx=max(res.mx,res1.mr+res2.ml);

     res.ml=max(res1.ml,res1.smm+res2.ml);

     res.mr=max(res2.mr,res2.smm+res1.mr);

     return res;

 }

 int main(){

     n=read();

     int i,j,x,y;

     for(i=;i<=n;i++)data[i]=read();

     Build(,n,);

     m=read();

     tmp0.ml=tmp0.mr=tmp0.mx=-1e9;tmp0.smm=;

     for(i=;i<=m;i++){

         x=read();y=read();

         printf("%d\n",query(x,y,,n,).mx);

     }

     return ;

 }