#include<fstream>
#define max(a,b) (a < b ? b : a)
#define min(a,b) (a < b ? a : b)
#define nmax  100006
using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

struct Nod{int max, min, smax;};
int N, a[nmax * 2 +100], M, start, finish, maxp, minp;
Nod arb[nmax * 2 + 100];

void update(int nod, int st, int dr)
{
    if(st == dr)
    {
        arb[nod].max = a[st];
        arb[nod].min = a[st - 1];
        arb[nod].smax = arb[nod].max - arb[nod].min;
        return;
    }
    int mij = (st + dr)/2;
    update(nod * 2, st, mij);
    update(nod * 2+ 1, mij + 1,dr);
    arb[nod].max = max(arb[nod * 2].max, arb[nod * 2 + 1].max);
    arb[nod].min = min(arb[nod * 2].min, arb[nod * 2 + 1].min);
    arb[nod].smax = max(arb[nod * 2 + 1].max - arb[nod *2].min, max(arb[nod * 2].smax, arb[nod * 2 + 1].smax));


}

void query(int nod, int st, int dr)
{
    if(start <= st && dr<= finish)
    {
        maxp = max(maxp, arb[nod].smax);
              if(minp != (1<<25)){

        maxp = max(maxp, arb[nod].max - minp);
         minp = min(minp, arb[nod].min);
      }
      else
      minp = arb[nod].min;
        return ;

    }
    int mij = (st + dr)/2;
    if(mij >= start )
        query(nod * 2,st, mij);
    if(mij < finish)
        query (nod * 2 + 1,mij + 1, dr);
}

void read()
{
    fin >>N >>M;
    for(int i = 1 ;i <= N; i++)
    {
        fin >>a[i];
        a[i] += a[i- 1];

    }
    update(1,1,N);
    while(M)
    {
        fin>>start >>finish;
        maxp = -100000;
        minp = (1<<25);
        query(1,1,N);
        fout<< maxp <<'\n';
        --M;
    }

}
int main()
{
    read();
    fin.close();
    return 0;

}