#include <stdio.h>
#define NMAX (1<<18)
#define MAX(a,b) (((a)>(b)) ? (a):(b))

int V[NMAX], N, M, P1, P2;
long long SumT[NMAX<<1], SumSt[NMAX<<1], SumDr[NMAX<<1], SumMax[NMAX<<1];
long long Max, S, INF;

void update(int x, int val)
{
        int nod = NMAX+x, l, r;

        SumSt[nod] = SumDr[nod] = SumMax[nod] = SumT[nod] = val;

        while (nod>1) {
              nod = nod>>1;
              l = nod<<1; r = l+1;
              SumSt[nod] = MAX(SumSt[l], SumT[l]+SumSt[r]);
              SumDr[nod] = MAX(SumDr[r], SumT[r]+SumDr[l]);
              SumMax[nod] = MAX( MAX(SumMax[l], SumMax[r]), SumSt[r]+SumDr[l]);
              SumT[nod] = SumT[l]+SumT[r];
        }
}

void query(int p1, int p2, int nod)
{
        int mij, l, r;

        if (p1>p2) return;

        if (P1 <= p1 && p2 <= P2)
        {
                if (S<0) S = 0;
                Max = MAX(Max, MAX(S+SumSt[nod], SumMax[nod]));
                S = MAX(S+SumT[nod], SumDr[nod]);
                return;
        }
        if ( (p1 <= P1 && P1 <= p2) || (p1 <= P2 && P2 <= p2) )
        {
                mij = (p1+p2)>>1; l = nod<<1; r = l+1;
                query(p1, mij, l);
                query(mij+1, p2, r);
        }
}

int main()
{
        int i, j, k, t;
        long long a = (1<<30), b = (1<<30);

        INF = a*b*4;

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

        scanf("%d %d", &N, &M);
        for (i = 1; i <= N; i++) scanf("%d", V+i);

        for (i = 1; i <= N; i++) update(i, V[i]);

        for (k = 1; k <= M; k++)
        {
                scanf("%d %d", &i, &j);
                Max = -INF; S = 0;
                if (i<=j)
                   P1 = i, P2 = j;
                else P1 = j, P2 = i;
                query(0, NMAX-1, 1);
                printf("%lld\n", Max);
        }

        return 0;
        
}