#include <cstdio>
#define LS (nod << 1)
#define RS ((nod << 1) + 1)
const char iname[] = "sequencequery.in";
const char oname[] = "sequencequery.out";
const int MAXN = 200005;

int n, m;
long long s, maxval;
struct{
    long long best, left, right, entire;
}tree[4*MAXN];

long long Maxim(const long long a, const long long b){
    if(a > b)   return a;
    return b;
}

void update(int nod, int L, int R, int pos, int val){
    if(L == R){tree[nod].best = tree[nod].left = tree[nod].right = tree[nod].entire = val; return;}
    int mij = (L+R)>>1;
    if(pos <= mij)update(LS, L, mij, pos, val);
    else update(RS, mij+1, R, pos, val);

    tree[nod].best  = Maxim(Maxim(tree[LS].best, tree[RS].best), tree[LS].right + tree[RS].left);
    tree[nod].left  = Maxim(tree[LS].left, tree[LS].entire + tree[RS].left);
    tree[nod].right = Maxim(tree[RS].right, tree[RS].entire + tree[LS].right);
    tree[nod].entire = tree[LS].entire + tree[RS].entire;
}
void querry(int nod, int L, int R, int Lt, int Rt){
    if(L > Rt || R < Lt) return;
    if(Lt <= L && R <= Rt){
        maxval = Maxim(maxval, Maxim(s + tree[nod].left, tree[nod].best));
        s = Maxim(s + tree[nod].entire, tree[nod].right);
        return;
    }
    int mij = (L+R)/2;
    querry(LS, L, mij, Lt, Rt);
    querry(RS, mij+1, R, Lt, Rt);
}
void read(){
    for(int i = 1; i <= n; ++i){
        int readin;
        scanf("%d", &readin);
        update(1,1,n,i,readin);
    }
}
void solve(){
    for(int i = 0; i < m; ++i){
        int a, b;
        scanf("%d %d", &a, &b);
        s = 0;
        maxval = -(1<<17);
        querry(1,1,n,a,b);
        printf("%lld\n", maxval);
    }
}
int main()
{
    freopen(iname, "r", stdin);
    freopen(oname, "w", stdout);
    scanf("%d %d\n", &n, &m);
    read();
    solve();
    return 0;
}