#include <iostream>
//#include <fstream>
using namespace std;

#define INF -0x3f3f3f3f

int x,y,sol,SMax,i,N,M,nr[100000],j,k,st,dr,poz;
int main()
{
    ifstream cin("sequencequery.in");
    ofstream cout("sequencequery.out");
    cin>>N>>M;
    for (i=1;i<=N;++i)
        cin>>nr[i];
    for (i=1;i<=M;++i)
    {
        SMax=0;
        sol=INF;
        cin>>x>>y;
        for (j=x;j<=y;++j)
        {
            if (SMax<0) SMax=nr[j];
                else SMax+=nr[j];
            if (SMax>sol) sol=SMax;
        }
        cout<<sol<<"\n";
    }
    return 0;
}