#include <fstream>

using namespace std;

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

const int Dim = 100001;
long long AintL[Dim * 4],AintR[Dim * 4],n,A[Dim],m,AintM[Dim * 4],AintS[Dim * 4],s,ma;
 void Update(long long nod, long long le, long long ri , long long poz, long long val) {

    if ( le == ri) {
   	 AintL[nod] = AintR[nod] = AintM[nod] = AintS[nod] = val;
   	 return;
    }

    long long mj = ( le + ri ) / 2;
    if ( mj >= poz)
   	 Update(nod * 2, le , mj, poz, val);
    else
   	 Update(nod * 2 + 1, mj + 1 , ri, poz, val);
    AintS[nod] = AintS[nod * 2] + AintS[nod * 2 + 1];
    AintM[nod] = max(AintR[nod * 2] + AintL[nod * 2 + 1], max(AintM[nod * 2], AintM[nod * 2 + 1]));
    AintL[nod] = max(AintL[nod * 2], AintS[nod * 2] + AintL[nod * 2 + 1]);
    AintR[nod] = max(AintR[nod * 2 + 1], AintS[nod * 2 + 1] + AintR[nod * 2]);
}

void Query(long long nod, long long le , long long ri, long long x, long long y) {

    if (  x <= le and ri <= y) {

   	 ma = max(ma, AintM[nod]);
   	 ma = max(ma, s + AintL[nod]);
   	 s = max(s + AintS[nod], AintR[nod]);

   	 return;
    }

    long long mj = ( le + ri ) / 2;
    if ( x <= mj)
   	 Query(nod * 2, le, mj , x, y);
    if ( y >= mj + 1)
   	 Query( nod * 2 + 1, mj + 1, ri, x, y);
}

int main() {

    fin >> n >> m;
    for ( long long i = 1; i <= n; ++i)
   	 fin >> A[i], Update(1,1,n,i,A[i]);
    long long x,y;
    for ( ; m > 0; --m) {
   	 fin >> x >> y;
   	 ma = - 1LL << 50;
   	 s = 0;
   	 Query(1,1,n,x,y);
   	 fout << ma << "\n";
    }
}