//ALEXANDRU MICLEA
 
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <time.h>
#include <iomanip>
#include <deque>
#include <math.h>
#include <cmath>
#include <assert.h>
#include <stack>
#include <bitset>
#include <random>
#include <chrono>
#include <assert.h>
 
using namespace std;
using ll = long long;
 
#include <fstream>
//ifstream cin("input.in"); ofstream cout("output.out");
ifstream cin("sequencequery.in"); ofstream cout("sequencequery.out");
 
//VARIABLES

struct node{
    int pref, suf, sum, ans;
} gr[400005];

//FUNCTIONS

node ssm(node st, node dr){
    node ret;

    ret.pref = max (st.pref, st.sum + dr.pref);
    ret.suf = max (dr.suf, dr.sum + st.suf);
    ret.sum = st.sum + dr.sum;
    ret.ans = max (max(st.ans, dr.ans), st.suf + dr.pref);

    return ret;
}

node make_node(int val){
    node ret;

    ret.sum = val;

    ret.pref = ret.suf = ret.ans = val;
    return ret;
}

void update(int nod, int st, int dr, int pos, int val){
    if (st == dr){
        gr[nod] = make_node(val);
        return;
    }

    int mid = st +  dr;
    mid /= 2;

    if (pos <= mid) update (nod * 2, st, mid, pos, val);
    else update (nod * 2 + 1, mid + 1, dr, pos, val);

    gr[nod] = ssm(gr[nod * 2], gr[nod * 2 + 1]);
}

int query (int nod, int st, int dr, int ST, int DR){

    if (st >= ST && dr <= DR) return gr[nod].ans;

    int mid = st + dr;
    mid /= 2;
    int ANS = -1e9;

    if (ST <= mid) ANS = max (ANS, query(nod * 2, st, mid, ST, DR));
    if (mid < DR) ANS = max (ANS, query(nod * 2 + 1, mid + 1, dr, ST, DR));

    return ANS;
}

//MAIN
 
int main() {
    
    int n, m; cin >> n >> m;

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

    for (int i = 1; i <= m; i++){
        int a , b; cin >> a >> b;
        cout << query(1,1,n,a,b) << '\n';
    }

    return 0;
}