#include <fstream>

using namespace std;
ifstream f ("sequencequery.in");
ofstream g ("sequencequery.out");
int n,m,i,j,x,y,poz1,poz2,p,scMax,sc,a[100000];
int main()
{
    f>>n>>m;
    for(i=1; i<=n; i++)
        f>>a[i];
    for(i=1; i<=m; i++)
    {
        f>>x>>y;
        scMax=-1500000;
        sc=0;
        poz1=poz2=p=x;
        for(j=x; j<=y; j++)
        {
            sc+=a[j];
            if(sc<=a[j])
            {
                sc=a[j];

            }
            if(sc>scMax)
            {
                scMax=sc;
            }
        }
        g<<scMax<<'\n';
    }
    return 0;
}