#include <fstream>

using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
void citire ( int &,int &);
void ssm (int ,int );
int max ( int ,int );
int mvect(int,int);
int v[100007],best[100007];
int main()
{
    int n,k,i,x,y;
    citire(n,k);
    ssm (1,n);
    for(i=0;i<k;i++)
    {
        fin>>x>>y;
        fout<<mvect(x,y)<<"\n";
    }
    return 0;
}

void ssm ( int a, int b)
{
    int i;
    best[a]=v[a];
    //maxim=v[a];
    for (i=a+1;i<=b;i++)
    //{
        best[i]=max(v[i],best[i-1]+v[i]);
        //if(best[i]>maxim)
            //maxim=best[i];
    //}
        //fout<<maxim<<"\n";
}


void citire (int &n,int &k)
{
    int i;
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>v[i];
}
int max ( int a,int b)
{
    if (a>b)
        return a;
    return b;
}

int mvect (int a,int b)
{
    int maxim=-100001;
    for(int i=a;i<=b;i++)
        if (best[i]>maxim)
            maxim=best[i];
    return maxim;
}