#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
//#include <bits/stdc++.h>
#define in fin
#define out fout

using namespace std;

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

struct aint{
    int pref, suf, sum, ssm;
};

aint merge(aint a, aint b){
    aint c;

    if(a.ssm == INT_MIN) return b;

    c.pref = max(a.pref, a.sum + b.pref);
    c.suf  = max(b.suf, b.sum + a.suf);

    c.ssm = max( max(a.ssm, b.ssm), a.suf + b.pref );
    c.sum = a.sum + b.sum;

    return c;
}

aint a[4 * 100001];
int v[100001];

void build(int l, int r, int p){
    if(l == r){
        a[p].ssm = v[l];
        a[p].suf = v[l];
        a[p].pref = v[l];
        a[p].sum = v[l];
        return;
    }

    int m = (l + r) / 2;
    build(l, m, p * 2);
    build(m + 1, r, p * 2 + 1);

    a[p] = merge(a[p * 2], a[p * 2 + 1]);
}

aint sol;

void query(int l, int r, int p, int lq, int rq){
    if(lq <= l && r <= rq){
        sol = merge(sol, a[p]);
        // cout <<  pref << "(pref) " << a[p].suf << "(suf)\n";
        return;
    }

    int m = (l + r) / 2;
    if(lq <= m) query(l, m, p * 2, lq, rq);
    if(rq  > m) query(m + 1, r, p * 2 + 1, lq, rq);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q; in >> n >> q;

    for(int i = 1; i <= n; i++) in >> v[i];
    build(1, n, 1);

    for(int i = 0; i < q; i++){
        int l, r; in >> l >> r;
        sol.pref = 0;
        sol.ssm = INT_MIN;
        sol.suf = 0;
        sol.sum = 0;

        // cout << "facem : ( " << l << " , " << r << " )\n";

        query(1, n, 1, l, r);
        out << sol.ssm << '\n';
    }

    return 0;
}