#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define FIN "sequencequery.in"
#define FOUT "sequencequery.out"
#define NMAX 600005
#define SUP 0x3f3f3f3f3fLL
int val,pos,ST[NMAX],CT[NMAX],DR[NMAX],SUM[NMAX],elem[NMAX];
long long rasp,S,a,b;
void creare(int nod,int l,int r)
{if(l==r) {ST[nod]=CT[nod]=DR[nod]=elem[l];
           SUM[nod]=elem[l];
           return;}
 else {int md=(l+r)>>1;
       creare(nod<<1,l,md);
       creare(nod<<1|1,md+1,r);
       ST[nod]=max((long long)ST[nod<<1],(long long)SUM[nod<<1]+ST[nod<<1|1]);
       DR[nod]=max((long long)DR[nod<<1|1],(long long)SUM[nod<<1|1]+DR[nod<<1]);
       CT[nod]=max(CT[nod<<1],max(CT[nod<<1|1],DR[nod<<1]+ST[nod<<1|1]));
       SUM[nod]=SUM[nod<<1]+SUM[nod<<1|1];
      }
     }
void query(int nod,int l,int r)
{if(a<=l && r<=b) {
                   rasp=max(rasp,max((long long)S+ST[nod],(long long)CT[nod]));
                   S=max((long long)DR[nod],(long long)S+SUM[nod]);
                   }
 else {int md=(l+r)>>1;
       if(a<=md) query(nod<<1,l,md);
       if(md<b) query(nod<<1|1,md+1,r);}}
int main()
{freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
int n,m;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&elem[i]);
creare(1,0,n-1);
for(;m;m--)
 {scanf("%d %d",&a,&b);
         S=rasp=-SUP;
         a--;b--;
         query(1,0,n-1);
         printf("%lld\n",rasp);

        }

 return 0;
    }