#include <fstream>

using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
int a[100003],sc,smax,n,m,x,y,i,j;
int main()
{
    f>>n>>m;
    for(i=1; i<=n; ++i)
        f>>a[i];
    for(j=1; j<=m; ++j)
    {
        f>>x>>y;
        sc=0;
        smax=-100000;
        for(i=x; i<=y; ++i)
        {
            sc+=a[i];
            if(sc<a[i])
            {
                sc=a[i];
            }
            if(sc>smax)
            {
                smax=sc;
            }
        }
        g<<smax<<'\n';
    }
    return 0;
}