#include <bits/stdc++.h>
using namespace std;

const long long MAX = 1e15;

struct node {
    long long s, l, r, ans;
};

node t[1<<20];
int n, q;

node get(node chl, node chr) {
    node p;
    p.l = max(chl.l, chl.s+chr.l);
    p.r = max(chr.r, chr.s+chl.r);
    p.s = chl.s + chr.s;
    p.ans = max({p.l,p.r,chl.r+chr.l,chl.ans,chr.ans});
    return p;
}

void build(int idx) { for (;idx;idx>>=1) t[idx] = get(t[idx*2],t[idx*2+1]); }
long long query(int idl, int idr) {
    node resl = {-MAX,-MAX,-MAX,-MAX};
    node resr = resl;
    for (; idl < idr; idl >>= 1, idr >>= 1) {
        if (idl&1) resl = get(resl,t[idl++]);
        if (idr&1) resr = get(t[--idr],resr);
    }
    return get(resl,resr).ans;
}

int main() {
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        t[n+i] = {x,x,x,x};
        build((n+i)/2);
    }
    while(q--) {
        int left, right;
        cin >> left >> right;
        cout << query(left+n-1,right+n) << "\n";
    }
}