using namespace std;

#include<algorithm>

#define FILES

#ifdef FILES
#include <fstream>
ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
#else
#include <iostream>
#endif

const int NMAX=100001;
const long long INF=1LL<<60;
long long s,mx;
int n,m,x,y;
struct AINT{
    long long total,best,left,right;
};
AINT u[NMAX*3];
int v[NMAX];

void build(int node,int lf,int rt){

    if(lf==rt){
        u[node].total=u[node].best=u[node].left=u[node].right=v[lf];
        return;
    }

    build(node*2 , lf , (lf+rt)/2);
    build(node*2+1 , (lf+rt)/2+1 , rt);

    u[node].total=u[node*2].total+u[node*2+1].total;
    u[node].best=max(max(u[node*2].best,u[node*2+1].best),u[node*2].right+u[node*2+1].left);
    u[node].left=max(u[node*2].left,u[node*2].total+u[node*2+1].left);
    u[node].right=max(u[node*2+1].right,u[node*2].right+u[node*2+1].total);

    return;
}

void query(int node,int lf,int rt){

    if(rt<x||y<lf)
        return;
    if(x<=lf&&y>=rt){
        mx=max(mx,max(u[node].best,s+u[node].left));
        s=max(s+u[node].total,u[node].right);
        return;
    }

    query(node*2 , lf , (lf+rt)/2);
    query(node*2+1 , (lf+rt)/2+1 , rt);

    return;
}

int main()
{
    cin>>n>>m;

    for(int i=1;i<=n;i++)
        cin>>v[i];
    build(1,1,n);

    for(int i=1;i<=m;i++){
        mx=-INF;
        s=0;
        cin>>x>>y;
        query(1,1,n);
        cout<<mx<<'\n';
    }

    return 0;
}