#include <fstream>
using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
const int MAXN = 4e5 + 5;
int aints[MAXN]; 
int aintsm[MAXN];
int aintl[MAXN] ;
int aintr[MAXN]; 
int ma,s;

void update(int nod, int l , int r, int poz, int val) {
    if(l == r) {
    aintl[nod] = aintr[nod] = aints[nod] = aintsm[nod] = val;        
    return;
}
int mj = (l + r) >> 1;
if(mj >= poz)
    update(nod*2,l,mj,poz,val);
else
    update(nod*2+1,mj+1,r,poz,val);
aints[nod] =  aints[nod*2] + aints[nod*2+1];
aintsm[nod] = max(aintsm[nod*2],max(aintsm[nod*2+1],aintr[nod*2] + aintl[nod*2+1])); 
aintl[nod]= max(aintl[nod*2],aints[nod*2] + aintl[nod*2+1]);
aintr[nod]= max(aintr[nod*2+1],aintr[nod*2+1] + aintr[nod*2]);

}

void query(int nod, int l, int r, int x, int y){
    if(l >= x and r <= y){
        ma = max(ma,aintsm[nod]);
        ma = max(ma,s + aintl[nod]);
        s = max(s+aints[nod],aintr[nod]);
    return;
}
    int mj = (l + r) >> 1;
    if(x <= mj)
    query(nod*2,l,mj,x,y);
    if(y > mj)
    query(nod*2+1,mj+1,r,x,y);
}
int n,m,a[MAXN],x,y;
int main() {

    fin >> n >> m;
    for ( int i = 1; i <= n; ++i) {
        fin >> a[i];
        update(1,1,n,i,a[i]);
}
    for ( int i = 1; i <= m; ++i) {
        fin >> x >> y;
        ma = - (1<<30);
        s = 0;
        query(1,1,n,x,y);
        fout << ma << "\n";
}
}