#include <fstream>

using namespace std;

long long arbs[500010], arbd[500010], sum[500010], a[100010], arb[500010], s, sol;
int x, y, i, n, m;
void build(int nod, int l, int r)
{
    if(l == r)
    {
        arbs[nod] = arbd[nod] = sum[nod] = arb[nod] = a[l];
        return;
    }
    int mid = (l+r)/2;
    build(2*nod, l, mid);
    build(2*nod+1, mid+1, r);
    sum[nod] = sum[2*nod]+sum[2*nod+1];
    arb[nod] = max(arb[2*nod], arb[2*nod+1]);
    arb[nod] = max(arb[nod], arbd[2*nod]+arbs[2*nod+1]);
    arbd[nod] = max(arbd[2*nod+1], arbd[2*nod]+sum[2*nod+1]);
    arbs[nod] = max(arbs[2*nod], arbs[2*nod+1]+sum[2*nod]);

}
void query(int nod, int l, int r)
{
    if(x <= l and r <= y)
    {
        if(arb[nod] > sol) sol = arb[nod];
        if(s > sol and x != l) sol = s;
        if(s < 0) s = 0;
        if(s + arbs[nod] > sol) sol = s + arbs[nod];
        s += sum[nod];
        if(arbd[nod] > s) s = arbd[nod];
        return;
    }
    int mid = (l+r)/2;
    if(x <= mid) query(2*nod, l, mid);
    if(y > mid) query(2*nod+1, mid+1, r);
}
int main()
{
    ifstream fi("sequencequery.in");
    ofstream fo("sequencequery.out");
    fi >> n >> m;
    for(i = 1; i <= n; i++) fi >> a[i];
    build(1, 1, n);
    while(m--)
    {
        fi >> x >> y;
        s = 0;
        sol = a[x];
        query(1, 1, n);
        if(s > sol) s = sol;
        fo << sol << "\n";
    }
    return 0;
}