#include <cstdio>

#define Nmax 200005
#define Amax 524289
#define INF 1000000000
#define ll int
#define max(a, b) ((a) >= (b) ? (a) : (b))

int n, m, a, b;
ll sir[Nmax];
ll ST[Amax], DR[Amax], BEST[Amax], SUM[Amax];
ll S, sol;

void citire()
{
    int i;
    scanf("%d %d\n", &n, &m);
    
    for (i = 1; i <= n; ++i)
        scanf("%d", &sir[i]);
}

void init(int nod, int st, int dr)
{
    if (st == dr)
    {
        DR[nod] = sir[st];
        ST[nod] = sir[st];
        SUM[nod] = sir[st];
        BEST[nod] = sir[st];
    }
    else
    {
        int mij = (st + dr) / 2;
        
        init(nod*2, st, mij);
        init(nod*2+1, mij+1, dr);
        
        ST[nod] = max(ST[nod*2], ST[nod*2+1] + SUM[nod*2]);
        DR[nod] = max(DR[nod*2+1], DR[nod*2] + SUM[nod*2+1]);
        BEST[nod] = max(max(BEST[nod*2], BEST[nod*2+1]), DR[nod*2] + ST[nod*2+1]);
        SUM[nod] = SUM[nod*2] + SUM[nod*2+1];
    }
}

void query(int nod, int st, int dr)
{
    if (a <= st && dr <= b)
    {
        sol = max(sol, S + ST[nod]);
        S = max(S + SUM[nod], DR[nod]);
        sol = max(sol, S);
        sol = max(sol, BEST[nod]);
    }
    else
    {
        int mij = (st + dr) / 2;
        
        if (a <= mij)
            query(nod*2, st, mij);
        if (mij < b)
            query(nod*2+1, mij+1, dr);
    }
}

void solve()
{
    int i;
    
    init(1, 1, n);
    
    for (i = 1; i <= m; ++i)
    {
        scanf("%d %d\n", &a, &b);
        S = sol = -INF;
        query(1, 1, n);
        printf("%d\n", sol);
    }
    
}

int main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    citire();
    solve();
    return 0;
}