#include <fstream>

using namespace std;
const int N=1e5;

long long aint[4*N];
int a[N];

void update(int node, int st, int dr, int poz, int x){
    int mij;
    if(st>poz || dr<poz)
        return;
    if(st==dr){
        aint[node]=x;
        return;
    }
    mij=(st+dr)/2;
    if(mij>=poz)
        update(2*node+1, st, mij, poz, x);
    else
        update(2*node+2, mij+1, dr, poz, x);
    aint[node]=aint[2*node+1]+aint[2*node+2];
}

int main()
{
    ifstream fin("sequencequery.in");
    ofstream fout("sequencequery.out");
    int n, m, i, x, y;
    long long sum, summax, summin;
    fin>>n>>m;
    for(i=0; i<n; i++){
        fin>>a[i];
        update(0, 0, n-1, i, a[i]);
    }
    for(i=0; i<m; i++){
        fin>>x>>y;
        sum=0;
        summax=-1e18;
        summin=0;
        for(x--; x<y; x++){
            sum+=a[x];
            if(summax<sum-summin)
                summax=sum-summin;
            if(summin>sum)
                summin=sum;
        }
        fout<<summax<<"\n";
    }
    return 0;
}