#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

const int maxn = 1e5+5, inf = 0x3f3f3f3f;

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

int n, m, i, x, y;
int v[maxn], sp[maxn];

int k;

struct sq
{
    int mx, mn, best;
}a[320];

void sqrtk()
{
    k = sqrt(n);
    int i, j = 1, sum = 0;
    for(i = 1; i <= n; i ++) {
        sp[i] = sp[i-1] + v[i];
        if(i > (j * (n / k))) {
            ++j;
            a[j] = {-inf, inf, -inf};
            sum = 0;
            a[j].mn = sp[i-1];
        }
        sum += v[i];

        if(sum > a[j].best)
        { a[j].best = sum; }

        if(sum < 0)
            sum = 0;

        if(sp[i] > a[j].mx) {
            a[j].mx = sp[i];
        } if(sp[i] < a[j].mn) {
            a[j].mn = sp[i];
        }
    }
}

inline int land(int x) {
    return ((x - 1) / (n / k) + 1);
}
inline int area(int s) {
    return ((n / k) * (s - 1) + 1);
}

int query(int x, int y)
{
    int i, sum;
    int fx, fy;
    fx = land(x);
    fy = land(y);

    if(fx == fy)
    {
        sum = 0;
        int rez = -inf;
        for(i = x; i <= y; i ++)
        {
            sum += v[i];
            if(sum > rez) {
                rez = sum;
            }
            if(sum < 0) { sum = 0; }
        }
        return rez;
    }

    int as = area(fx + 1) - 1, af = area(fy - 1) + (n / k);
    while(af > y) {
        af -= (n - k);
    }
    int first = -inf, fm = inf, last = -inf, lm = -inf;

    sum = 0;
    fm = sp[x-1];
    for(i = x; i <= as; i ++)
    {
        sum += v[i];
        if(sum > first) {
            first = sum;
        }
        if(sum < 0) { sum = 0; }
        if(sp[i] < fm) { fm = sp[i]; }
    }

    sum = 0;
    for(i = af; i <= y; i ++) {
        sum += v[i];
        if(sum > last)
            { last = sum; }
        if(sum < 0) { sum = 0; }
        if(sp[i] > lm) { lm = sp[i]; }
    }

    int mnn = fm, rez = -inf;
    if(first > rez) { rez = first; }
    for(i = fx + 1; i <= fy - 1; i ++)
    {
        if(a[i].mx - mnn > rez) { rez = a[i].mx - mnn; }
        if(a[i].mn < mnn) {mnn = a[i].mn; }
        if(a[i].best > rez) { rez = a[i].best; }
    }
    if(lm - mnn > rez) { rez = lm - mnn; }
    if(last > rez) { rez = last; }

    return rez;
}

int main()
{
    f >> n >> m;
    for(i = 1; i <= n; i ++) {
        f >> v[i];
    }

    sqrtk();

    while(m --)
    {
        f >> x >> y;
        g << query(x, y) << '\n';
    }

    f.close();
    g.close();
    return 0;
}
//sequencequery nt 3