//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[100005];

//FUNCTIONS

node make_node(int val){
    node ret;

    ret.ans = ret.pref = ret.suf = ret.sum = val;

    return ret;
}

node join(node a, node b){
    node ret;
    
    ret.sum = a.sum + b.sum;
    ret.pref = max (a.pref, a.sum + b.pref);
    ret.suf = max (b.suf, b.sum + a.suf);
    ret.ans = max (max(a.ans, b.ans) , a.suf + b.pref);

    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);
    if (mid < dr) update (nod * 2 + 1, mid + 1, dr, pos, val);

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

node query (int nod, int st, int dr, int ST, int DR){
    if (st == ST && dr == DR) return gr[nod];
    else {
        node ret = make_node(-1e9);

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

        if (ST <= mid){
            ret = query(nod * 2, st, mid, ST, min(DR, mid));
        } 
        if (mid < DR){
            if (ret.ans == -1e9){
                ret = query (nod * 2 + 1, mid + 1, dr, max(ST,mid + 1), DR);
            }
            else {
                ret = join (ret, query (nod * 2 + 1, mid + 1, dr, max(ST,mid + 1), DR));
            }
        }

        return ret;
    }
}

//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;
        node ANS = query(1, 1, n, a, b);
        //node ANS = gr[b];

        cout << ANS.ans << '\n';
    }
    
}