#include <fstream>
#include <cstdio>
#define NR 100005
#define VAL 262145
#define INF 1000000000000000

using namespace std;

struct arbore
{
    long long STOT, SBEG, SEND, SBEST;
};

arbore arb[VAL];

int N, M, i, j;
int v[NR], be, en;
int SEGM[VAL], K;
long long MID, END;
long long DPMID, DPEND;

void Initialize(int nod, int be, int en)
{
    if (be==en)
      arb[nod].STOT=arb[nod].SBEG=arb[nod].SEND=arb[nod].SBEST=v[be];
    else
    {
        int mid=(be+en) / 2;
        Initialize(2*nod, be, mid);
        Initialize(2*nod+1, mid+1, en);
        arb[nod].STOT=arb[2*nod].STOT+arb[2*nod+1].STOT;
        arb[nod].SBEG=max(arb[2*nod].SBEG, arb[2*nod].STOT+arb[2*nod+1].SBEG);
        arb[nod].SEND=max(arb[2*nod+1].SEND, arb[2*nod].SEND+arb[2*nod+1].STOT);
        arb[nod].SBEST=max(arb[2*nod].SBEST, arb[2*nod+1].SBEST);
        arb[nod].SBEST=max(arb[nod].SBEST, arb[2*nod].SEND+arb[2*nod+1].SBEG);
    }
}

void Split_Interval(int nod, int st, int dr, int be, int en)
{
    if (max(st, be)>min(dr, en))
      return;
    if (be<=st && dr<=en)
    {
        SEGM[++K]=nod;
        return;
    }
    int mid=(st+dr) / 2;
    Split_Interval(2*nod, st, mid, be, en);
    Split_Interval(2*nod+1, mid+1, dr, be, en);
}

long long Query()
{
    MID=arb[SEGM[0]].SBEST;
    END=arb[SEGM[0]].SEND;
    long long ANS=max(MID, END);
    for (int i=1; i<=K; i++)
    {
        DPMID=max(arb[SEGM[i]].SBEST, END+arb[SEGM[i]].SBEG);
        DPEND=max(arb[SEGM[i]].SEND, END+arb[SEGM[i]].STOT);
        MID=DPMID;
        END=DPEND;
        ANS=max(ANS, DPMID);
        ANS=max(ANS, DPEND);
    }
    return ANS;
}

int main()
{
    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]);
    Initialize(1, 1, N);
    for (i=1; i<=M; i++)
    {
        scanf("%d %d", &be, &en);
        K=-1;
        Split_Interval(1, 1, N, be, en);
        printf("%lld\n", Query());
    }
    return 0;
}