#include <bits/stdc++.h>
using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");


struct nod{
    long long prefix,sufix,sumtot,sumopt;
}arbint[400005];

int n,k,a,b;
long long v[100005];

nod unite_arb(nod a, nod b) {
    nod c;
    c.prefix = max(a.prefix,a.sumtot+b.prefix);
    c.sufix = max(b.sufix,b.sumtot+a.sufix);
    c.sumtot = a.sumtot + b.sumtot;
    c.sumopt = max(a.sumopt,max(b.sumopt,a.sufix+b.prefix));
    return c;
}

void create_arb(int poz, int st, int dr) {
    if (st==dr) {
        arbint[poz].prefix = arbint[poz].sufix = arbint[poz].sumopt = arbint[poz].sumtot = v[st];
        return;
    }
    int mij = (st+dr)/2;
    create_arb(2*poz,st,mij);
    create_arb(2*poz+1,mij+1,dr);
    arbint[poz] = unite_arb(arbint[2*poz],arbint[2*poz+1]);
}

nod query(int poz, int st, int dr) {
    if (st>b || dr<a) {
        nod c;
        c.prefix = c.sufix = c.sumopt = c.sumtot = -INT_MAX;
        return c;
    }
    if (a<=st && b>=dr) {
        return arbint[poz];
    }
    int mij = (st+dr)/2;
    nod arbst = query(2*poz,st,mij);
    nod arbdr = query(2*poz+1,mij+1,dr);
    return unite_arb(arbst,arbdr);
}

int main()
{
    f >> n >> k;
    for (int i=1;i<=n;i++) {
        f >> v[i];
    }
    create_arb(1,1,n);
    for (int i=1;i<=k;i++) {
        f >> a >> b;
        nod rez = query(1,1,n);
        g << rez.sumopt << '\n';
    }
    return 0;
}