#include <stdio.h>
#define TMAX (1<<17)
#define NMAX 100100
#define INF 666666666

int Tmax[2*TMAX], Tmin[2*TMAX], T[2*TMAX];
int N, M, V[NMAX], S[NMAX];
int A, B, Max, Min, pmax, pmin, sol;

void update1(int x)
{
        int nod = TMAX+x;

        while (nod > 1)
        {
                nod /= 2;
                T[nod] = T[2*nod];
                if (V[ T[nod] ] < V[ T[2*nod+1] ]) T[nod] = T[2*nod+1];
        }
}

void update2(int x)
{
        int nod = TMAX+x;

        while (nod > 1)
        {
                nod /= 2;
                Tmax[nod] = Tmax[2*nod];
                if (S[ Tmax[nod] ] < S[ Tmax[2*nod+1] ]) Tmax[nod] = Tmax[2*nod+1];
        }
}

void update3(int x)
{
        int nod = TMAX+x;

        while (nod > 1)
        {
                nod /= 2;
                Tmin[nod] = Tmin[2*nod];
                if (S[ Tmin[nod] ] > S[ Tmin[2*nod+1] ]) Tmin[nod] = Tmin[2*nod+1];
        }
}

void query1(int p1, int p2, int nod)
{
        int mij;

        if (A <= p1 && p2 <= B)
        {
                if (Max < V[T[nod]]) Max = V[T[nod]];
                return;
        }
        if ((p1 <= A && A <= p2) || (p1 <= B && B <= p2))
        {
                mij = (p1+p2)>>1;
                query1(p1, mij, 2*nod);
                query1(mij+1, p2, 2*nod+1);
        }
}

void query2(int p1, int p2, int nod)
{
        int mij;

        if (A <= p1 && p2 <= B)
        {
                if (Max < S[Tmax[nod]])
                   Max = S[Tmax[nod]], pmax = Tmax[nod];
                return;
        }
        if ((p1 <= A && A <= p2) || (p1 <= B && B <= p2))
        {
                mij = (p1+p2)>>1;
                query2(p1, mij, 2*nod);
                query2(mij+1, p2, 2*nod+1);
        }
}

void query3(int p1, int p2, int nod)
{
        int mij;

        if (A <= p1 && p2 <= B)
        {
                if (Min > S[Tmin[nod]]) Min = S[Tmin[nod]], pmin = Tmin[nod];
                return;
        }
        if ((p1 <= A && A <= p2) || (p1 <= B && B <= p2))
        {
                mij = (p1+p2)>>1;
                query3(p1, mij, 2*nod);
                query3(mij+1, p2, 2*nod+1);
        }
}


int main()
{
        int i, j, k;

        freopen("sequencequery.in", "r", stdin);
        freopen("sequencequery2.out", "w", stdout);
        scanf("%d %d", &N, &M);
        for (i = 0; i < N; i++) scanf("%d", V+i);
        S[0] = V[0];
        for (i = 1; i < N; i++) S[i] = S[i-1]+V[i];

        for (i = 0; i < N; i++)
        {
                T[i+TMAX] = i;
                Tmax[i+TMAX] = Tmin[i+TMAX] = i;
        }

        for (i = 0; i < N; i++)
        {
                update1(i);
                update2(i);
                update3(i);
        }

        while (M--)
        {
             scanf("%d %d", &i, &j);
             if (i != j)
             {
                sol = -INF;
                
                A = i-1; B = j-1;
                Max = S[A]; pmax = A;
                query2(0, TMAX-1, 1);
                A = i-2; B = pmax;
                Min = S[A]; pmin = A;
                query3(0, TMAX-1, 1);
                if (pmax != pmin)
                {
                    sol = Max-Min;
                    if (i == 1 && sol < Max) sol = Max;
                }

                A = i-1; B = j-1;
                Min = S[A]; pmin = A;
                query3(0, TMAX-1, 1);
                A = pmin; B = j-1;
                Max = S[A]; pmax = A;
                query2(0, TMAX-1, 1);
                if ((sol < Max-Min) && (pmax != pmin))
                {
                    sol = Max-Min;
                    if (i == 1 && sol < Max) sol = Max;
                }
                
                A = i-1;  B = j-1;
                Max = V[A];
                query1(0, TMAX-1, 1);
                if (sol < Max) sol = Max;
             }
             else sol = V[i-1];
             printf("%d\n", sol);
        }

        return 0;

}