//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

ll v[100005];

struct node{
    ll pref, suf, sum, ans;
} gr[100005];

//FUNCTIONS

node make_node(ll val){
    node ret;
    ret.pref = ret.ans = ret.suf = ret.sum = val;
    return ret;
}

node ssm (node l, node r){
    node ret;

    ret.ans = max (max (l.ans, r.ans), l.suf + r.pref);
    ret.pref = max (l.pref, l.sum + r.pref);
    ret.suf = max (r.suf, r.sum + l.suf);
    ret.sum = l.sum + r.sum;

    return ret;
}

void build (ll nod, ll st, ll dr){
    if (st == dr){
        gr[nod] = make_node(v[st]);
        return;
    } 

    ll mid = (st + dr) / 2;

    build (nod * 2, st, mid);
    build (nod * 2 + 1, mid + 1, dr);
    
    gr[nod] = ssm (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), DR);
            }
            else {
                ret = ssm (ret, query (nod * 2 + 1, mid + 1, dr, max(ST,mid + 1), DR));
            }
        }

        return ret;
    }
}

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

    for (ll i = 1; i <= n; i++){
        ll val; cin >> val;
        v[i] = val;
    }

    build(1,1,n);

    for (ll i = 1; i <= m; i++){
        ll a, b; cin >> a >> b;
        node ANS = query(1, 1, n, a, b);

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