#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

int v[100005], n, m;
struct arbint{
    long long s, smax, st, dr;
}a[300005];

void calculate(int nod, int st, int dr){
    if (st == dr){
        a[nod].s = v[st];
        a[nod].smax = v[st];
        a[nod].st = v[st];
        a[nod].dr = v[st];
        return;
    }
    int mij = (st + dr) >> 1;
    int ls = 2 * nod, rs = ls + 1;
    calculate(ls, st, mij);
    calculate(rs, mij + 1, dr);
    a[nod].s = a[ls].s + a[rs].s;
    a[nod].smax = max(max(a[ls].smax, a[rs].smax), a[ls].dr + a[rs].st);
    a[nod].st = max(a[ls].st, a[ls].s + a[rs].st);
    a[nod].dr = max(a[rs].dr, a[rs].s + a[ls].dr);
}

long long f(int nod, int st, int dr, int qs, int qd, int x){
    if (x == 1){
        if (qs <= st && dr <= qd)
            return a[nod].st;
        int mij = (st + dr) >> 1;
        int ls = 2 * nod, rs = ls + 1;
        long long sol = f(ls, st, mij, qs, qd, x);
        if (qd > mij)
            sol = max(sol, a[ls].s + f(rs, mij + 1, dr, qs, qd, x));
        return sol;
    }
    else if (x == 2){
        if (qs <= st && dr <= qd)
            return a[nod].dr;
        int mij = (st + dr) >> 1;
        int ls = 2 * nod, rs = ls + 1;
        long long sol = f(rs, mij + 1, dr, qs, qd, x);
        if (qs <= mij)
            sol = max(sol, a[rs].s + f(ls, st, mij, qs, qd, x));
        return sol;
    }
    else{
        if (qs <= st && dr <= qd)
            return a[nod].smax;
        if (dr < qs || st > qd)
            return 0;
        int mij = (st + dr) >> 1;
        int ls = 2 * nod, rs = ls + 1;
        long long a1 = f(ls, st, mij, qs, qd, x), a2 = f(rs, mij + 1, dr, qs, qd, x);
        if (qd <= mij)
            return a1;
        else if (qs > mij)
            return a2;
        else
            return max(max(a1, a2), f(ls, st, mij, qs, qd, 2) + f(rs, mij + 1, dr, qs, qd, 1));

    }
}

int main(){
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
    calculate(1, 1, n);
    while (m--){
        int x, y;
        fin >> x >> y;
        fout << f(1, 1, n, x, y, 3) << '\n';
    }
    return 0;
}