# include <cstdio>
# include <algorithm>

# define INF -2000000000
# define fiu_st (nod<<1)
# define fiu_dr ((nod<<1)+1)
# define mij ((st+dr)>>1)
# define N 100010

using namespace std;

struct arb
{
    long long st,dr,sum,best;
}T[N],sol;
int a[N];
int i,n,m,x,y;

inline arb compute(arb x, arb y)
{
    if(x.best==INF) return y;
    if(y.best==INF) return x;

    arb T;
    T.sum=x.sum+y.sum;
    T.best=max(x.dr+y.st, max(x.best,y.best));
    T.st=max(x.st, x.sum+y.st);
    T.dr=max(y.dr, y.sum+x.dr);
    return T;
}

inline void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        T[nod].st=T[nod].dr=T[nod].sum=T[nod].best=a[st];
        return;
    }
    build(fiu_st,st,mij);
    build(fiu_dr,mij+1,dr);
    T[nod]=compute(T[fiu_st], T[fiu_dr]);
}

inline arb query(int nod, int st, int dr, int x, int y)
{
    if(x<=st && dr<=y) return T[nod];
    if(st!=dr)
    {
        arb q1,q2;
        q1.best=q2.best=INF;
        if(x<=mij) q1=query(fiu_st,st,mij,x,y);
        if(y>mij) q2=query(fiu_dr,mij+1,dr,x,y);
        return compute(q1,q2);
    }
}

int main()
{
	freopen("sequencequery.in", "r", stdin);
	freopen("sequencequery.out", "w", stdout);

    scanf("%d %d\n", &n, &m);
    for(i=1; i<=n; ++i) scanf("%d\n", &a[i]);
    build(1,1,n);

    while(m--)
    {
        scanf("%d %d\n", &x, &y);
        sol=query(1,1,n,x,y);
        printf("%lld\n", sol.best);
    }

	fclose(stdin);
	fclose(stdout);
	return 0;
}