#include <fstream>
#include <iostream>
#include <algorithm>
 
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
 
struct ARBORE{
    long long rbest,lbest,best,sum;
    ARBORE(){
        rbest = lbest = sum = best = -1000000;
    }
};
 
ARBORE ARB[400050];
int el,ind,N,st,dr,M;
 
void addel(int l,int r,int pos){
    if(l >= r){
        ARB[pos].lbest = ARB[pos].rbest = ARB[pos].sum = ARB[pos].best = el;
        return;
    }
     
    int mid = (l+r)/2;
    if(ind <= mid) addel(l,mid,pos*2);
    else addel(mid+1,r,pos*2+1);
     
}
 
void gen(int l,int r,int pos){
    if(l >= r) return;
 
    gen(l,(l+r)/2,pos*2);
    gen((l+r)/2+1,r,pos*2+1);
    ARB[pos].best = max(ARB[pos*2].best,max(ARB[pos*2+1].best,ARB[pos*2].rbest+ARB[pos*2+1].lbest));
    ARB[pos].sum = ARB[pos*2].sum + ARB[pos*2+1].sum;
    ARB[pos].lbest = max(ARB[pos*2].lbest,ARB[pos*2].sum+ARB[pos*2+1].lbest); 
    ARB[pos].rbest = max(ARB[pos*2+1].rbest,ARB[pos*2+1].sum+ARB[pos*2].rbest);
     
}
 
ARBORE querry(int l,int r,int pos){
    if(l >= st && r <= dr) return ARB[pos];
    ARBORE rs,a,b;
    int mid = (l+r)/2;
    if( st <= mid ) a = querry(l,mid,pos*2);
    if(dr > mid) b = querry(mid+1,r,pos*2+1);
    if(a.sum == -1000000) return b;
    if(b.sum == -1000000) return a;
    rs.best = max(a.best,max(b.best,a.rbest+b.lbest));
    rs.sum = a.sum + b.sum;
    rs.lbest = max(a.lbest,a.sum+b.lbest);
    rs.rbest = max(b.rbest,a.rbest + b.sum);
    return rs;
}
 
 
int main(){
    fin >> N >> M;
    for(ind = 1;ind<=N;ind++){
        fin >> el;
        addel(1,N,1);
    }
 
    gen(1,N,1);
     
    for(int i = 0;i<M;i++){
        fin >> st >> dr;
        fout << querry(1,N,1).best << '\n';
    }
     
     
    return 0;
}