#include<fstream>
#define NINF -1000000000000
using namespace std;

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

struct nod
{
    int st,dr;
    long long sum,sumdr,sumst,sumt;
    nod *left,*right;
}*root;

struct rez_query
{
    long long sum,sumdr,sumst,sumt;
};

nod* build(int st,int dr,int v[])
{
    nod *a;
    a=new nod;
    a->st=st;
    a->dr=dr;
    if(st==dr)
    {
        a->sum=a->sumdr=a->sumst=a->sumt=v[st];
        a->left=a->right=NULL;
        return a;
    }
    int mij=(st+dr)/2;
    a->left = build(st,mij,v);
    a->right = build(mij+1,dr,v);
    a->sumt = a->right->sumt + a->left->sumt;
    a->sum = max(a->left->sum,max(a->right->sum, a->left->sumdr + a->right->sumst));
    a->sumdr = max(a->right->sumdr,a->left->sumdr + a->right->sumt);
    a->sumst = max(a->left->sumst,a->left->sumt + a->right->sumst);
    return a;
}

rez_query query(int st,int dr,nod *nc)
{
    if(dr < nc->st || st > nc->dr)
        return {NINF,NINF,NINF,NINF};
    if(nc->st == nc->dr)
    {
        int val = nc->sum;
        return {val,val,val,val};
    }
    rez_query r1 = query(st,dr,nc->left);
    rez_query r2 = query(st,dr,nc->right);

    rez_query r = {max(r1.sum,max(r2.sum,r1.sumdr + r2.sumst)),-1,-1,r1.sumt + r2.sumt};
    if(dr >= nc->dr)
        r.sumdr = max(r2.sumdr,r1.sumdr + r2.sumt);
    if(st<= nc->st)
        r.sumst = max(r1.sumst,r1.sumt + r2.sumst);
    return r;
}


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