#include <bits/stdc++.h>
#define int long long

using namespace std;
ifstream fin ("sequencequery.in");
ofstream fout ("sequencequery.out");
int const INF=1e17;

struct arb{
  int sum,sum_mx,sum_r,sum_l;
};

arb ans;
arb aint[800020];
int v[200020];

void build_aint(int node,int l,int r){
  if(l==r)
  {
    aint[node]={v[l],v[l],v[l],v[l]};
    return ;
  }
  build_aint(2*node,l,(l+r)/2);
  build_aint(2*node+1,(l+r)/2+1,r);

  aint[node].sum=aint[2*node].sum+aint[2*node+1].sum;
  aint[node].sum_r=max(aint[2*node+1].sum_r,aint[2*node].sum_r+aint[2*node+1].sum);
  aint[node].sum_l=max(aint[2*node].sum_l,aint[2*node+1].sum_l+aint[2*node].sum);
  aint[node].sum_mx=max(max(aint[2*node].sum_mx,aint[2*node+1].sum_mx),aint[2*node].sum_r+aint[2*node+1].sum_l);
}

void query(int node,int l,int r,int x,int y)
{
  if(x<=l && r<=y)
  {
    arb aux=ans;

    ans.sum=aux.sum+aint[node].sum;
    ans.sum_r=max(aint[node].sum_r,aux.sum_r+aint[node].sum);
    ans.sum_l=max(aux.sum_l,aint[node].sum_l+aux.sum);
    ans.sum_mx=max(max(aux.sum_mx,aint[node].sum_mx),aux.sum_r+aint[node].sum_l);
    return ;
  }
    if(l>=r) return ;

    int mid=(l+r)/2;
    if(mid>=x)  query(2*node,l,mid,x,y);
    if(mid+1<=y) query(2*node+1,mid+1,r,x,y);
}


signed main()
{
    int n,q;

    fin>>n>>q;
    for(int i=1;i<=n;++i)
      fin>>v[i];

    build_aint(1,1,n);

    for(int i=1;i<=q;++i)
    {
        int x,y;
        fin>>x>>y;

        ans.sum=-INF;
        ans.sum_mx=-INF;
        ans.sum_r=-INF;
        ans.sum_l=-INF;

        query(1,1,n,x,y);
        fout<<ans.sum_mx<<"\n";
    }
    return 0;
}