#include <fstream>
#include <algorithm>
#define inf -(1LL << 60)
#define ll long long

using namespace std;

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

const int nmax = 1e5 + 5;

int n, m;
ll rsp, crt, s[4 * nmax], l[4 * nmax], r[4 * nmax], best[4 * nmax];

void init(){
    for(int i = 1; i <= 4 * n; i++)
        s[i] = l[i] = r[i] = best[i] = inf;
}

void update(int nod, int st, int dr, int pos, int val){
    if(st == dr){
        s[nod] = l[nod] = r[nod] = best[nod] = val;
        return;
    }

    int mid = (st + dr) / 2, x = nod * 2, y = nod * 2 + 1;

    if(pos <= mid)
        update(x, st, mid, pos, val);
    else
        update(y, mid + 1, dr, pos, val);

    l[nod] = max(l[x], s[x] + l[y]);
    r[nod] = max(r[y], s[y] + r[x]);
    s[nod] = s[x] + s[y];
    best[nod] = max({best[x], best[y], s[nod], r[x] + l[y]});
}

void query(int nod, int st, int dr, int x, int y){
    if(x <= st && dr <= y){
        rsp = max({rsp, crt + l[nod], best[nod]});
        crt = max(crt + s[nod], r[nod]);
        rsp = max(rsp, crt);

        return;
    }

    int mid = (st + dr) / 2;
    if(x <= mid)
        query(2 * nod, st, mid, x, y);
    if(mid < y)
        query(2 * nod + 1, mid + 1, dr, x, y);
}

void read(){
    fin >> n >> m;

    init();

    for(int i = 1; i <= n; i++){
        int val;
        fin >> val;
        update(1, 1, n, i, val);
    }
}

void solve(){
    while(m--){
        int x, y;
        fin >> x >> y;
        rsp = inf, crt = 0;
        query(1, 1, n, x, y);
        fout << rsp << "\n";
    }
}

int main()
{
    read();
    solve();

    return 0;
}