#include <fstream>

#define MAX 131072
#define leftSon (nod << 1)
#define rightSon ((nod << 1) + 1)
#define INF (1LL << 62)

using namespace std;

struct ArboreIntervale
{
    long long L, R, B, S;
}aInt[4 * MAX];

int v[MAX], x, y, n, q;
long long sum, maxim;

void build(int nod, int l, int r)
{
    if(l == r)
    {
        aInt[nod].L = aInt[nod].R = aInt[nod].B = aInt[nod].S = v[l];
        return;
    }
    int m = (l + r) >> 1;
    build(leftSon, l, m);
    build(rightSon, m + 1, r);
    aInt[nod].L = max(aInt[leftSon].L, aInt[leftSon].S + aInt[rightSon].L);
    aInt[nod].R = max(aInt[rightSon].R, aInt[rightSon].S + aInt[leftSon].R);
    aInt[nod].B = max(max(aInt[leftSon].B, aInt[rightSon].B), aInt[leftSon].R + aInt[rightSon].L);
    aInt[nod].S = aInt[leftSon].S + aInt[rightSon].S;
}

void query(int nod, int l, int r)
{
    if(x <= l && r <= y)
    {
        if(sum < 0) sum = 0;
        maxim = max(maxim, max(aInt[nod].B, aInt[nod].L + sum));
        sum = max(sum + aInt[nod].S, aInt[nod].R);
        return;
    }
    int m = (l + r) >> 1;
    if(x <= m) query(leftSon, l, m);
    if(m < y) query(rightSon, m + 1, r);
}

int main()
{
    ifstream in("sequencequery.in");
    in>>n>>q;
    for(int i = 1; i <= n; i++) in>>v[i];
    build(1, 1, n);
    ofstream out("sequencequery.out");
    for(int i = 1; i <= q; i++)
    {
        in>>x>>y;
        sum = 0;
        maxim = -INF;
        query(1, 1, n);
        out<<maxim<<"\n";
    }
    return 0;
}