#include <fstream>
#define inf  1111111111111111111
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int n,m;
struct swg
{ long long sum,s,d;
    long long maxi;
};
swg a[500005];

long long maxdr(int nd,int x,int y,int st,int dr)
{
    if(x==st&& y==dr)
        return a[nd].d;
    else
    { long long maxi; int mijl=(st+dr)/2;
      if(x>mijl)
        return maxdr(2*nd+1,x,y,mijl+1,dr);
      else
      { maxi=maxdr(2*nd+1,mijl+1,y,mijl+1,dr);
          maxi=max(maxi,a[2*nd+1].sum + maxdr(2*nd,x,mijl,st,mijl));
          return maxi;
      }
    }

}


long long maxst(int nd,int x,int y,int st,int dr)
{
    if(x==st && y==dr)
        return a[nd].d;
    else
    {
        long long maxi; int mijl=(st+dr)/2;
       if(y<=mijl) return maxst(2*nd,x,y,st,mijl);
       else
       { maxi=maxst(2*nd,x,mijl,st,mijl);
           maxi=max(maxi , a[2*nd].sum +maxst(2*nd+1,mijl+1,y,mijl+1,dr) );
           return maxi;
       }
    }


}

long long query(int nd,int x,int y,int st,int dr)
{
    if(x==st && y==dr)
        return a[nd].maxi;
    int mijl;
    mijl=(st+dr)/2;
    if(y<=mijl)
        return query(2*nd,x,y,st,mijl);
    if(x>mijl) return query(2*nd+1,x,y,mijl+1,dr);

    long long maxi;
        maxi=max(query(2*nd,x,mijl,st,mijl),query(2*nd+1,mijl+1,y,mijl+1,dr) );
        maxi=max(maxi,maxdr(2*nd,x,mijl,st,mijl)+maxst(2*nd+1,mijl+1,y,mijl+1,dr) );
 return maxi;
}
int main()
{    fin>>n>>m;
    int narb=1,i,x,y;
    while(narb<n) narb*=2;
    for(i=1;i<=n;++i)
        {fin>>a[i+narb-1].sum;  a[i+narb-1].maxi=a[i+narb-1].s=a[i+narb-1].d=a[i+narb-1].sum;}
    for(i=narb+n;i<=2*narb;++i)
        a[i].s=a[i].d=a[i].sum=a[i].maxi=-inf;
    for(i=narb-1;i>=1;--i)
    { a[i].sum=a[i*2].sum+a[i*2+1].sum;
        if(a[i*2+1].d==a[i*2+1].sum)
            a[i].d=max(a[i*2+1].d,a[i*2+1].d+a[i*2].d);
        else a[i].d=a[i*2+1].d;

        if(a[i*2+1].sum+a[i*2].d>a[i].d)
            a[i].d=a[i*2+1].sum+a[i*2].d;

        if(a[i*2].s==a[i*2].sum) a[i].s=max(a[i*2].s,a[i*2].s+a[i*2+1].s);
        else a[i].s=a[i*2].s;

        if(a[i*2].sum+a[i*2+1].s>a[i].s)
            a[i].s=a[i*2].sum+a[i*2+1].s;

        a[i].maxi=max(a[i*2].maxi,a[i*2+1].maxi);
        a[i].maxi=max(a[i].maxi,a[i].d); a[i].maxi=max(a[i].maxi,a[i].d);
        a[i].maxi=max(a[i].maxi,a[i*2].d+a[i*2+1].s);
    }
    for(i=1;i<=m;++i)
    { fin>>x>>y;
        fout<<query(1,x,y,1,narb)<<"\n";
    }


    return 0;
}