#include <cstdio>
#include <algorithm>
#define NMAX 100005
#define LL long long
#define DIM 10000

using namespace std;

struct elem
{
    LL sufix;
    LL prefix;
    LL sol;
    LL sum;
}arb[3*NMAX],ini,ans;

char buff[DIM];
int v[NMAX], n,i,caz,a,b, m,poz=0;

void citeste(int &numar)
{
     numar = 0;
     char semn='+';
     while (buff[poz] < '0' || buff[poz] > '9')
     {
          semn = buff[poz];
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
     while ('0'<=buff[poz] && buff[poz]<='9')
     {
          numar = numar*10 + buff[poz] - '0';
          if (++poz == DIM)
               fread(buff,1,DIM,stdin),poz=0;
     }
     if (semn == '-')
          numar = -numar;
}

void update(const int &st, const int &dr, const int &poz, const int &nod)
{
    if(st==dr)
    {
        arb[nod].sum=v[poz];
        arb[nod].prefix=v[poz];
        arb[nod].sufix=v[poz];
        arb[nod].sol=v[poz];
        return;
    }

    int mij=((st+dr)>>1);
    int sfiu=(nod<<1);
    int dfiu=((nod<<1)+1);

    if(poz<=mij)
        update(st,mij,poz,sfiu);
    if(poz>mij)
        update(mij+1,dr,poz,dfiu);

    arb[nod].sol = max(max(arb[sfiu].sol, arb[dfiu].sol), arb[sfiu].sufix + arb[dfiu].prefix);
    arb[nod].sum = arb[sfiu].sum + arb[dfiu].sum;
    arb[nod].prefix = max(arb[sfiu].prefix, arb[sfiu].sum + arb[dfiu].prefix);
    arb[nod].sufix = max(arb[sfiu].sufix + arb[dfiu].sum, arb[dfiu].sufix);
}

elem querry(const int &st, const int &dr, const int &st1, const int &dr1, const int &nod)
{
    if(st==st1 && dr==dr1)
        return arb[nod];

    int mij=((st+dr)>>1);
    //g<<mij<<" "<<st<<" "<<dr<<" "<<st1<<" "<<dr1<<"\n";
    if(dr1<=mij)
        return querry(st,mij,st1,dr1,(nod<<1));
    if(st1>mij)
        return querry(mij+1,dr,st1,dr1,((nod<<1)+1));

    elem temp1, temp2, temp3;

    temp1 = querry(st, mij, st1, mij, 2*nod);
    temp2 = querry(mij+1, dr, mij+1, dr1, 2*nod+1);
    temp3.sol = max(max(temp1.sol, temp2.sol), temp1.sufix + temp2.prefix);
    temp3.sum = temp1.sum + temp2.sum;
    temp3.prefix = max(temp1.prefix, temp1.sum + temp2.prefix);
    temp3.sufix = max(temp1.sufix + temp2.sum, temp2.sufix);
    return temp3;
}

void citire()
{
    freopen("sequencequery.in","r", stdin);

    citeste(n);
    citeste(m);

    for(i=1;i<=n;i++)
    {
        citeste(v[i]);
        update(1,n,i,1);
    }
}


void rezolvare()
{
    freopen("sequencequery.out", "w", stdout);

    for(i=1;i<=m;i++)
    {
        citeste(a);
        citeste(b);

        ans=querry(1,n,a,b,1);
        printf("%lld\n", ans.sol);
    }
}

int main()
{
    //initializare();
    citire();
    rezolvare();
    //for(i=1;i<=3*n;i++)
        //<<arb[i].sol<<" "<<arb[i].sum<<" "<<arb[i].prefix<<" "<<arb[i].sufix<<"\n";
}