# include <stdio.h>
# include <stdlib.h>

typedef struct CALUP {long int max_l, max_r, max_t, max_a;};
typedef struct NOD {CALUP m; NOD *stga,*drta;};
const long int MAXN=100000; //100000
long int v[MAXN+1],n,m;
typedef struct REQUEST {long int a,b;};
REQUEST req[MAXN+1];

NOD *rad;

int aloca_arb_dint(long int li, long int lf, NOD *q)
{
if (li==lf) return 0;
long int m=(li+lf)/2;
NOD *p;
p=(NOD*) malloc (sizeof(NOD));
(*p).stga=NULL;
(*p).drta=NULL;
(*q).stga=p;
aloca_arb_dint(li,m,p);
p=(NOD*) malloc (sizeof(NOD));
(*p).stga=NULL;
(*p).drta=NULL;
(*q).drta=p;
aloca_arb_dint(m+1,lf,p);
return 0;
}

long int max(long int a, long int b) { if (a>b) return a; return b;}

int populate_tree(long int li, long int lf, NOD *p)
{
NOD *fd=(*p).drta,*fs=(*p).stga;
if (li==lf)
	{
	(*p).m.max_l=v[li];
	(*p).m.max_r=v[li];
	(*p).m.max_t=v[li];
	(*p).m.max_a=v[li];
	return 0;
	}
else
	{
	long int m=(li+lf)/2;
	populate_tree(li ,m ,fs);
	populate_tree(m+1,lf,fd);
	//populate the actual level
	(*p).m.max_l=max((*fs).m.max_l,(*fs).m.max_t+(*fd).m.max_l);
	(*p).m.max_r=max((*fd).m.max_r,(*fd).m.max_t+(*fs).m.max_r);
	(*p).m.max_t=(*fs).m.max_t+(*fd).m.max_t;
		(*p).m.max_a=max((*p).m.max_l,(*p).m.max_r);
		(*p).m.max_a=max((*p).m.max_a,(*fs).m.max_r+(*fd).m.max_l);
		(*p).m.max_a=max((*p).m.max_a,(*fs).m.max_a);
		(*p).m.max_a=max((*p).m.max_a,(*fd).m.max_a);
	}
return 0;
}

void citire()
{
FILE *f=fopen("sequencequery.in","r");
fscanf(f,"%ld%ld",&n,&m);
long int i;
for (i=1;i<=n;i++) fscanf(f,"%ld",&v[i]);
for (i=1;i<=m;i++) fscanf(f,"%ld%ld",&req[i].a,&req[i].b);
fclose(f);
}

int querry(long int a, long int b, long int li, long int lf, NOD *p,CALUP &c)
{
long int m=(li+lf)/2;
CALUP sol;
if (li==a&&lf==b) {c=(*p).m; return 0;}
if (m>=b) {querry(a,b,li , m,(*p).stga,sol);c=sol;return 0;}
if (m< a) {querry(a,b,m+1,lf,(*p).drta,sol);c=sol;return 0;}
CALUP auxs,auxd;
querry(a,m,li,m,(*p).stga,auxs);
querry(m+1,b,m+1,lf,(*p).drta,auxd);
sol.max_t=auxs.max_t+auxd.max_t;
sol.max_l=max(auxs.max_l,auxs.max_t+auxd.max_l);
sol.max_r=max(auxd.max_r,auxd.max_t+auxs.max_r);
	sol.max_a=max(auxs.max_a,auxd.max_a);
	sol.max_a=max(sol.max_a,auxs.max_r+auxd.max_l);
c=sol;
return 0;
}

void scrie()
{
FILE *g=fopen("sequencequery.out","w");
long int i,sol;
CALUP c;
for (i=1;i<=m;i++)
	{
	querry(req[i].a,req[i].b,1,n,rad,c);
	fprintf(g,"%ld\n",c.max_a);
	}
fcloseall();
}

void print_tree(long int li, long int lf, NOD *p)
{
CALUP c=(*p).m;
printf("%ld %ld == max_t=%ld max_l=%ld max_r=%ld max_a=%ld\n",li,lf,c.max_t,c.max_l,c.max_r,c.max_a);
long int m=(li+lf)/2;
if (li!=lf)
	{
	print_tree(li,m,(*p).stga);
	print_tree(m+1,lf,(*p).drta);
	}
}

int main()
{
citire();
rad=(NOD*) malloc (sizeof(NOD));
(*rad).stga=NULL;
(*rad).drta=NULL;
aloca_arb_dint(1,n,rad);
populate_tree(1,n,rad);
//print_tree(1,n,rad);
scrie();
return 0;
}