#include<fstream>
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
int n,m,i,x,y,a[100001],max1,sum;
void query(int x,int y)
{
    max1=a[x];
    sum=a[x];
    for(i=x+1;i<=y;i++)
    {
        if(sum<0)
          sum=a[i];
        else
          sum+=a[i];
        if(sum>max1)
          max1=sum;
    }
    g<<max1<<"\n";
}
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
      f>>a[i];
    while(m)
    {
        m--;
        f>>x>>y;
        query(x,y);
    }
    return 0;
}