#include <fstream>
#include <vector>

using namespace std;

const int N = 1e5;
const int P2MAX = (1 << 18);
const long long INF = (1LL << 60);

struct t {
    long long sum = -INF;
    long long sum_st = -INF;
    long long sum_dr = -INF;
    long long sum_tot = -INF;
};

t aint[P2MAX];
int poz, val, a, b;
vector<int> v;

void actualizare(int p, int st, int dr) {
    if (st == dr) {
        aint[p].sum = aint[p].sum_st = aint[p].sum_dr = aint[p].sum_tot = val;
        return;
    }
    int m = (st + dr) / 2;
    if (poz <= m)
        actualizare(2 * p, st, m);
    else
        actualizare(2 * p + 1, m + 1, dr);
    aint[p].sum = max(aint[2 * p].sum, aint[2 * p + 1].sum);
    aint[p].sum = max(aint[2 * p].sum_dr + aint[2 * p + 1].sum_st, aint[p].sum);
    aint[p].sum_st = max(aint[2 * p].sum_st, aint[2 * p].sum_tot + aint[2 * p + 1].sum_st);
    aint[p].sum_dr = max(aint[2 * p + 1].sum_dr, aint[2 * p + 1].sum_tot + aint[2 * p].sum_dr);
    aint[p].sum_tot = aint[2 * p].sum_tot + aint[2 * p + 1].sum_tot;
}

void interogare(int p, int st, int dr) {
    if (st >= a && dr <= b) {
        v.push_back(p);
        return;
    }
    int m = (st + dr) / 2;
    if (a <= m)
        interogare(2 * p, st, m);
    if (b > m)
        interogare(2 * p + 1, m + 1, dr);
}

int main() {
    ifstream in("sequencequery.in");
    ofstream out("sequencequery.out");
    int n, q;
    in >> n >> q;
    for (int i = 1; i <= n; ++i) {
        in >> val;
        poz = i;
        actualizare(1, 1, n);
    }
    while (q--) {
        in >> a >> b;
        interogare(1, 1, n);
        long long rez = -INF;
        for (int i = 0; i < v.size() - 1; ++i)
            for (int j = i + 1; j < v.size(); ++j) {
                long long s = aint[v[i]].sum_dr + aint[v[j]].sum_st;
                for (int k = i + 1; k < j; ++k)
                    s += aint[v[k]].sum_tot;
                rez = max(rez, s);
            }
        for (int i = 0; i < v.size(); ++i)
            rez = max(rez, aint[v[i]].sum);
        v.clear();
        out << rez << '\n';
    }
    in.close();
    out.close();
    return 0;
}