# 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
# define T 400020

using namespace std;

struct arb
{
    long long st,dr,sum,best;
} t[T],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;
}