#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;
 
inline 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);
    scanf("%d %d",&n,&q);
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d",&x);
        t[n+i] = {x,x,x,x};
        build((n+i)/2);
    }
    while(q--) {
        int left, right;
        scanf("%d %d",&left,&right);
        cout << query(left+n-1,right+n) << "\n";
    }
}