#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

ll n, m, x, y;

struct Arbll {
    struct El {
        ll sum, inc, sf, smx;
    };

    vector<El> v;
    Arbll(ll n) : v(n * 4) {
    }

    void add(ll x, ll i, ll st = 1, ll dr = n, ll idx = 1) {
        if (st == dr) {
            v[idx].sum = x;
            v[idx].inc = x;
            v[idx].sf = x;
            v[idx].smx = x;
            return;
        }

        ll mij = (st + dr) / 2;
        if (i <= mij) {
            add(x, i, st, mij, idx * 2);
        } else {
            add(x, i, mij + 1, dr, idx * 2 + 1);
        }

        v[idx].sum = v[idx * 2].sum + v[idx * 2 + 1].sum;
        v[idx].inc = max(v[idx * 2].inc, v[idx * 2].sum + v[idx * 2 + 1].inc);
        v[idx].sf = max(v[idx * 2 + 1].sf, v[idx * 2 + 1].sum + v[idx * 2].sf);
        v[idx].smx =
            max(max(v[idx * 2].smx, v[idx * 2 + 1].smx), v[idx * 2].sf + v[idx * 2 + 1].inc);
    }

    void get(ll i, ll j, ll st = 1, ll dr = n, ll idx = 1) {
        if (i <= st && dr <= j) {
            rez = max(rez, max(s + v[idx].inc, v[idx].smx));
            s = max(s + v[idx].sum, v[idx].sf);
            return;
        }

        ll mij = (st + dr) / 2;
        if (i <= mij) {
            get(i, j, st, mij, idx * 2);
        }
        if (j > mij) {
            get(i, j, mij + 1, dr, idx * 2 + 1);
        }
    }
    ll rez, s;
};

int main() {
    fin >> n >> m;
    Arbll a(n);

    for (ll i = 1; i <= n; i++) {
        fin >> x;
        a.add(x, i);
    }

    for (ll i = 0; i < m; i++) {
        fin >> x >> y;
        a.s = 0;
        a.rez = LONG_LONG_MIN;
        a.get(x, y);
        fout << a.rez << "\n";
    }
}