#include <stdio.h>

#define NMAX 100001
#define MMAX 100001

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

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

// O(N)
void build(int nod, int l, int r)
{
    if (l == r)
    {
       /* if (nr[l] > 0)
            A[nod] = nr[l];
        else
            A[nod] = 0;*/
        B[nod] = C[nod] = A[nod] = nr[l];
        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;

// 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("%d", &nr[i]), ++i);

    build(1, 1, N);

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

        printf("%d\n", max(max(C[n1], C[n2]), B[n1]+A[n2]));
    }
}