#include<fstream>
#include<iostream>
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
int smax,i,m,j,n,u,p,p1,s,a[100005];
int x,y;
int main()
{
   f>>n>>m;
   for(i=1;i<=n;i++) f>>a[i];
   for(j=1;j<=m;j++)
   { f>>x>>y;
    smax=-1000000000;
    s=0;p1=x;
    for(i=x;i<=y;i++)
    {
        s+=a[i];
        if(s>smax) {smax=s; u=i;p=p1;}
        if(s<0){p1=i+1;s=0;}
    }
    g<<smax<<'\n';
   }
    return 0;
}