#include <iostream>
#include <fstream>
#define DN 400005
#define LL long long
using namespace std;

LL a[DN],b[DN],c[DN],d[DN],sum,rez;
int n,m,gls,gld,poz,el;



void update(int vn, int ls, int ld) {
    if(ls==ld) {
        a[vn]=b[vn]=c[vn]=el;
        d[vn]=el;
        return;
    }
    int m=(ls+ld)>>1,fs=vn<<1;
    if(poz<=m) update(fs,ls,m);
    else update(fs+1,m+1,ld);
    a[vn]=max(a[fs],d[fs]+a[fs+1]);
    b[vn]=max(b[fs]+d[fs+1],b[fs+1]);
    c[vn]=max(max(c[fs],c[fs+1]),b[fs]+a[fs+1]);
    d[vn]=d[fs]+d[fs+1];
}

void query(int vn, int ls, int ld) {
    if(ls==ld) {
       // if(0>sum) sum=0;
        rez=max(rez,max(sum+a[vn],c[vn]));
        sum=max(sum+d[vn],b[vn]);
        return;
    }
    int m=(ls+ld)>>1,fs=vn<<1;
    if(gls<=m) query(fs,ls,m);
    if(gld>m) query(fs+1,m+1,ld);
}

int main()
{
    ifstream f("sequencequery.in");
    ofstream g("sequencequery.out");
    f>>n>>m;
    for(int i=1; i<=n; ++i) {
        poz=i; f>>el;
        update(1,1,n);
    }
    for(int i=1; i<=m; ++i) {
        sum=rez=-9999999999LL;
        f>>gls>>gld;
        query(1,1,n);
        g<<rez<<'\n';
    }
    return 0;
}