#include <stdio.h>
#include <iostream>
#define INF 999999999
using namespace std;
FILE *in,*out;

int n,m,lf,rg;
int v[100002];

struct name{
    int tot,l,r,ans;
}ai[400002];

void read(){
    fscanf(in,"%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        fscanf(in,"%d",&v[i]);
}

void update(int node, int left, int right){
    if(left==right){
        ai[node].l=ai[node].r=ai[node].ans=ai[node].tot=v[left];
        return;
    }
    int mij=(left+right)/2;
    update(node*2,left,mij);
    update(node*2+1,mij+1,right);

    ai[node].l=max(ai[node*2].l,ai[node*2].tot+ai[node*2+1].l);
    ai[node].r=max(ai[node*2+1].r,ai[node*2+1].tot+ai[node*2].r);
    ai[node].tot=ai[node*2].tot+ai[node*2+1].tot;
    ai[node].ans=max(ai[node*2].ans,max(ai[node*2+1].ans,ai[node*2+1].l+ai[node*2].r));
}

name querry(int node, int left, int right){
    if(right<lf || left>rg){
        name sol;
        sol.ans=sol.l=sol.r=sol.tot=-INF;
        return sol;
    }
    if(left>=lf && right<=rg){
        return ai[node];
    }
    int mij=(left+right)/2;
    name sol1,sol2,sol;
    sol1=querry(node*2,left,mij);
    sol2=querry(node*2+1,mij+1,right);
    sol.l=max(sol1.l,sol1.tot+sol2.l);
    sol.r=max(sol2.r,sol2.tot+sol1.r);
    sol.tot=sol1.tot+sol2.tot;
    sol.ans=max(sol1.ans,max(sol2.ans,sol1.r+sol2.l));
    return sol;
}

void solve(){
    update(1,1,n);
    for(int i=1;i<=m;i++){
        fscanf(in,"%d %d",&lf,&rg);
        name sol;
        sol=querry(1,1,n);
        fprintf(out,"%d\n",sol.ans);
    }
}

int main(){
    in=fopen("sequencequery.in","r");
    out=fopen("sequencequery.out","w");
    read();
    solve();
    return 0;
}