#include <cstdio>
#include <algorithm>
#define FIN "maxq.in"
#define FOUT "maxq.out"
#include <vector>
#include <algorithm>
#define NM 200100
using namespace std;
#define max(a, b) ((a) > (b) ? (a) : (b))
int N, M;
int v[NM];
long long A[4*NM], B[4*NM], C[4*NM], Sum[4*NM];
int ThePosition, TheValue;
void build(int E, int Left, int Right){
	if (Left == Right) {
		A[E] = B[E] = C[E] = max(v[Left], 0);
		Sum[E] = v[Left];
		return;
	}
	int Middle=(Left+Right)>>1,left=E<<1,right=left+1;
        build(left,Left,Middle);
	    build(right, Middle+1,Right);
    A[E] = max(A[left], Sum[left]+A[right]);
	B[E] = max(B[left]+Sum[right], B[right]);
	C[E] = max(max(C[left], C[right]), B[left]+A[right]);
    Sum[E] = Sum[left]+Sum[right];
}
void update(int E, int Left, int Right){
	if (Left == Right) {
		A[E] = B[E] = C[E] = max(TheValue, 0);
		Sum[E] = TheValue;
		return;
	}
	int Middle=(Left+Right)>>1,left=E<<1,right=left+1;
	if (ThePosition <= Middle)
        update(left,Left,Middle);
	else
	    update(right, Middle+1,Right);
    A[E] = max(A[left], Sum[left]+A[right]);
	B[E] = max(B[left]+Sum[right], B[right]);
	C[E] = max(max(C[left], C[right]), B[left]+A[right]);
    Sum[E] = Sum[left]+Sum[right];
}
int Start, Finish;
long long ans, S;
void query(int E, int Left, int Right){
	if (Start <= Left && Right <= Finish) {
		if (S < 0)
            S = 0;
		ans = max(ans, max(S+A[E], C[E]));
		S = max(S+Sum[E], B[E]);
		return;
	}
	int Middle=(Left+Right)>>1;
	if (Start <= Middle)  query(E<<1,Left,Middle);
	if (Middle < Finish) query((E<<1)|1, Middle+1,Right);
}
class rmq{
    private:
        int n,i;
    vector< vector <int> > arb;
    vector<int> logx;
    void logar(){
        int i,x=1,y=0;
        for (i=1;i<=n;++i){
            if (i<(x<<1))
                logx[i]=y;
            else{
                x<<=1;
                logx[i]=++y;
            }
        }
    }
    public:
        void build(vector<int> param,int (*comparator)(int a,int b)){
            int i,j,log;
            n=param.size()-1;
            arb.resize(n+2);
            logx.resize(n+2);
            logar();
            for (log=0;(1<<log)<=n;++log);
            for (i=1;i<=n;++i){
                arb[i].resize(log+2,0);
                arb[i][0]=param[i];
            }
            for (i=n;i;--i)
                for (j=1;i+(1<<j)<=n+1;++j)
                    arb[i][j]=comparator(arb[i][j-1],arb[i+(1<<(j-1))][j-1]);
        }
        int query(int a,int b,int (*comparator)(int a,int b)){
            int log;
            log=logx[b-a+1];
            return comparator(arb[a][log],arb[b-(1<<log)+1][log]);
        }
};
rmq R;
int cmp(int a,int b){
    return max(a,b);
}
vector<int> aa;
int main(){
	int i, t, v1, v2;
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out", "w", stdout);
	scanf("%d%d", &N, &M);
	aa.push_back(0);
	for (i = 1; i <= N; ++i){
		scanf("%d", &v[i]);
		aa.push_back(v[i]);
	}
	build(1,1,N);
	R.build(aa,cmp);
	while (M--) {
		scanf("%d %d", &v1, &v2);
			S = ans = 0;
			Start = v1;
			Finish = v2;
			query(1, 1, N);
			if (ans==0)
			    printf("%d\n",R.query(v1,v2,cmp));
			else
                printf("%lld\n", ans);
	}
	return 0;
}