#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=a[x];
        sc=a[x];
        poz1=poz2=p=x;
        for(j=x; j<=y; j++)
        {
            sc+=a[j];
            if(sc<=a[j])
            {
                sc=a[j];
                p=j;
            }
            if(sc>scMax)
            {
                scMax=sc;
                poz1=p;
                poz2=j;
            }
        }
        g<<scMax<<'\n';
    }
    return 0;
}