#include <bits/stdc++.h>
using namespace std;

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

struct tree_node{
    
    long long sum,pmax,smax,scmax;
}v[400005];

int n,i,y,m,h[100005],a,b;

tree_node updatenode(tree_node l, tree_node d){
    
    tree_node cn;
    
    cn.sum=l.sum+d.sum;
    
    cn.pmax=max(l.pmax,l.sum+d.pmax);
    
    cn.smax=max(d.smax,d.sum+l.smax);
    
    cn.scmax=max({l.smax+d.pmax,l.scmax,d.scmax});
    
    return cn;
}

void build(int nod, int st, int dr){
    
    if(st==dr){
        v[nod]={h[st],h[st],h[st],h[st]};
    }
    else{
        int mid=(st+dr)/2;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);
        
        v[nod]=updatenode(v[2*nod],v[2*nod+1]);
    }
}

tree_node query(int nod, int st, int dr, int a, int b){
    
    if(a<=st && dr<=b)
    return v[nod];
    
    else{
        int mid=(st+dr)/2;
        
        if(b<=mid)return query(2*nod,st,mid,a,b);
        
        if(mid+1<=a)return query(2*nod+1,mid+1,dr,a,b);
        
        tree_node l = query(2*nod,st,mid,a,b);
        tree_node d =query(2*nod+1,mid+1,dr,a,b);
        
       return updatenode(l,d);
        
    }
}

int main(){
    
    fin>>n>>m;
    
    for(i=1;i<=n;i++)
    fin>>h[i];
    
    build(1,1,n);
    
    for(i=1;i<=m;i++){
        fin>>a>>b;
        
        fout<<query(1,1,n,a,b).scmax<<'\n';
    }
}