#include <stdio.h>
#define NM 100010

long v[NM];
long a[NM], b[NM], c[NM], d[NM];
long long s, sol;
long n, m;
//a[i] az i. nodhoz tartozo intervallum osszege
//b[i] az i. nodban levo intervallum maximuma
//c[i] az i. nodban levo intervallum balrol maximuma
//d[i] az i. nodban levo intervallum jobbrol maximuma

inline long max(long a, long b)
{
    return a>b?a:b;
}

void build(long nod, long e, long u)
{
    if (e==u)
    {
	a[nod]=b[nod]=c[nod]=d[nod]=v[e]; 
    }
    else
    {
	int mid = (e+u)>>1;
	int ie = 2*nod;
	int iu = 2*nod+1;

	build(ie, e, mid);
	build(iu, mid+1, u);

	a[nod] = a[ie] + a[iu];
	b[nod] = max(max(b[ie],b[iu]), d[ie] + c[iu]);
	c[nod] = max(c[ie], a[ie] + c[iu]);
	d[nod] = max(d[iu], a[iu] + d[ie]);
    }
}

void query(long nod, long e, long u, long i, long j)
{
    if (i<=e && u<=j)
    {
	sol = max(max(s+c[nod],b[nod]), sol);
	s = max(s+a[nod], d[nod]); //lol
    }
    else
    {
	int mid=(e+u)>>1;
	int ie=2*nod;
	int iu=2*nod+1;

	if (i<=mid) query(ie, e, mid, i, j);
	if (mid<j) query(iu, mid+1, u, i, j);
    }
}

int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);

    scanf("%d%d", &n, &m);

    for (long i=1; i<=n; ++i)
	scanf("%d", v+i);

    build(1,1,n);

    for (long i=1; i<=m; ++i)
    {
	int x, y;
	scanf("%d%d", &x, &y);
	sol=v[x]; s=0; query(1,1,n, x, y);
	printf("%lld\n", sol);
    }

    return 0;
}