#include <bits/stdc++.h>
#define int64 long long
#define INF 100001
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
vector<int64> ts,tl,tr,tt;
int n,pos,a,b,val,m;
int64 sum,ss;
void update(int x,int left,int right)
{
    if(left==right)
    {
        tr[x]=tl[x]=tt[x]=val;
        ts[x]=val;
    }
    else{
        int mid=(left+right)/2;
        if(pos<=mid)update(2*x,left,mid);
        else update(2*x+1,mid+1,right);
        tl[x]=max(tl[2*x],ts[2*x]+tl[2*x+1]);
        tr[x]=max(tr[2*x+1],ts[2*x+1]+tr[2*x]);
        tt[x]=max(tl[2*x+1]+tr[2*x],max(tt[2*x],tt[2*x+1]));
        ts[x]=ts[2*x]+ts[2*x+1];
    }
}
void query(int x,int left,int right)
{
    if(a<=left && b>=right)
    {
        sum=max(sum,max(ss+tl[x],tt[x]));
        ss=max(ss+ts[x],tr[x]);
    }
    else{
        int mid=(left+right)/2;
        if(a<=mid)query(2*x,left,mid);
        if(b>mid)query(2*x+1,mid+1,right);
    }
}
int main()
{
    in>>n>>m;
    ts=tt=tl=tr=vector<int64>(4*n+1);
    for(int i=1;i<=n;i++)
    {
        in>>val;pos=i;
        update(1,1,n);
    }
    for(;m;m--)
    {
        in>>a>>b;
        ss=0;sum=-INF;
        query(1,1,n);
        out<<sum<<'\n';
    }
    return 0;
}