#include <stdio.h>

#define NMAX 400001
#define MMAX 100001
#define INF 0x3f3f3f3f

int N, M;
long long nr[NMAX];
long long A[2*NMAX], B[2*NMAX], C[2*NMAX], S[2*NMAX];

inline int max(long long a, long long b)
{
    if (a>b)
        return a;
    else
        return b;
}

// O(N)
void build(int nod, int l, int r)
{
    if (l == r)
    {
        A[nod] = B[nod] = C[nod] = S[nod] = nr[l];
    }
    else
    {
        int mid = (l+r) >> 1;
        build(2*nod, l, mid);
        build(2*nod+1, mid+1, r);

        A[nod] = max(A[2*nod], A[2*nod+1]+S[2*nod]);
        B[nod] = max(B[2*nod+1], B[2*nod]+S[2*nod+1]);
        C[nod] = max(max(C[2*nod], C[2*nod+1]), A[2*nod+1]+B[2*nod]);
        S[nod] = S[2*nod] + S[2*nod+1];
    }
}

int a,b;
int n1,n2;
long long ans, SS;

void query(int n, int l, int r) // a, b
{
	if (a <= l && r <= b)
	{
		if (SS < 0) SS = 0;
		ans = max(ans, max(SS+A[n], C[n]));
		SS = max(SS+S[n], B[n]);
	}
	else
	{
        int mid = (l+r) >> 1;
		if (a <= mid) query(2*n,    l, mid);
		if (b >  mid) query(2*n+1, mid+1,  r);
	}
}


// O(logN)
/*void query(int nod, int l, int r)
{
    if (a<=l && r<=b)
    {
        if (!n1)
            n1 = nod;
        else
            n2 = nod;
    }
    else
    {
        int mid = (l+r) >> 1;
        if (a<=mid)
            query(2*nod, l, mid);
        if (mid<b)
            query(2*nod+1, mid+1, r);
    }
}*/

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

    scanf("%d %d", &N, &M);
    for (int i = 1; i<=N; scanf("%lld", &nr[i]), ++i);

    build(1, 1, N);

    for (int i = 1; i<=M; ++i)
    {
        scanf("%d %d", &a, &b);
        n1 = n2 = SS = ans = 0;
        ans = -INF;
        query(1, 1, N);
        if (!n2)
            n2 = n1;

        //ans = max(C[n1], C[n2]);
        //if (n1!=n2)
        //    ans = max(ans, B[n1]+A[n2]);
        //printf("%d\n", max(max(C[n1], C[n2]), B[n1]+A[n2]));
        printf("%lld\n", ans);
    }
}