#include <iostream>
#include <fstream>
#include <cstring>
#define inf 10000000001
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

 struct arbint
 { long long v,l,r,s; };

 int n,m,k;
 long long sol=0,last;

 arbint a[400069];

 void Update(int nod,int st,int dr,int ind,int x)
 { int mid=(st+dr)/2;

    if (st==dr)
     { a[nod].v=a[nod].l=a[nod].r=a[nod].s=x; return;}

    if (ind<=mid) Update(nod*2,st,mid,ind,x);
     else Update(nod*2+1,mid+1,dr,ind,x);

    a[nod].s= a[2*nod].s + a[2*nod+1].s;
    a[nod].l= max(a[2*nod].l , a[2*nod].s + a[2*nod+1].l);
    a[nod].r= max(a[2*nod+1].r, a[2*nod+1].s + a[2*nod].r);
    a[nod].v= max(a[2*nod].v, max(a[2*nod+1].v , a[2*nod].r + a[2*nod+1].l));

 }

 void Query(int nod,int st,int dr,int x,int y)
 { int mid=(st+dr)/2;

    if (x<=st && dr<=y)
    {  long long act=0;
        k++;

       act=max(a[nod].r,a[nod].s+last);

       sol=max(sol,max(act,last+a[nod].l));

       sol=max(sol,a[nod].v);

       last=act;
    }
    else
    {
   if (st==dr) return;
   if (x<=mid) Query(2*nod,st,mid,x,y);
   if (y>mid) Query(2*nod+1,mid+1,dr,x,y);
    }
 }

int main()
{ int n,i,el,sx,sy;
    f>>n>>m;

    for(i=1;i<=n;i++)
    { f>>el;
        Update(1,1,n,i,el);
    }


    for(i=1;i<=m;i++)
    { f>>sx>>sy;
        k=0; last=0;
       sol=-inf;
      Query(1,1,n,sx,sy);
        g<<sol<<"\n";
    }

    return 0;
}