#include <stdio.h>
#define INF 1LL * 1000000000 * 1000000000
#define nMax 100001
#define l 2*node
#define r 2*node+1
using namespace std;
int n, m;
int v[nMax];
long long Sol, Suma;
long long St[4*nMax], Dr[4*nMax], Mid[4*nMax], Sum[4*nMax];
long long max(long long a, long long b)
{
if(a<b)
return b;
return a;
}
void read()
{
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++)
scanf("%d", &v[i]);
}
void verif(int node, int st, int dr)
{
int mid=st+(dr-st)/2;
St[node]=St[l];
if(Sum[l]+St[r]>St[node])
St[node]=Sum[l]+St[r];
Dr[node]=Dr[r];
if(Sum[r]+Dr[l]>Dr[node])
Dr[node]=Sum[r]+Dr[l];
Mid[node]=max(Dr[l]+St[r], max(Mid[l], Mid[r]));
Sum[node]=Sum[l]+Sum[r];
}
void build(int node, int st, int dr)
{
if(st==dr)
{
St[node]=Dr[node]=Mid[node]=Sum[node]=v[st];
return;
}
int mid=st+(dr-st)/2;
build(l, st, mid);
build(r, mid+1, dr);
verif(node, st, dr);
}
void query(int node, int st, int dr, int pozst, int pozdr)
{
if(st>=pozst && dr<=pozdr)
{
Sol=max(Sol, Mid[node]);
if(Suma<0)
Suma=0;
Sol=max(Sol, Suma+St[node]);
Suma=Dr[node];
return;
}
int mid=st+(dr-st)/2;
if(pozst<=mid)
query(l, st, mid, pozst, pozdr);
if(pozdr>mid)
query(r, mid+1, dr, pozst, pozdr);
}
void solve()
{
int a, b;
build(1, 1, n);
for(int i=1;i<=m;i++)
{
scanf("%d%d", &a, &b);
Sol=-INF, Suma=0;
query(1, 1, n, a, b);
printf("%lld\n", Sol);
}
}
int main()
{
freopen("sequencequery.in", "r", stdin);
freopen("sequencequery.out", "w", stdout);
read();
solve();
return 0;
}