#include <bits/stdc++.h>
#define MAX_N (100000)

using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int n,m,aux;
struct Arb{long long S,D,C,Sum;}Ar[MAX_N*4];
void build(int,int,int);
void update(int,int,int,int,int);
Arb query(int,int,int,int,int);

int main()
{
	int v1,v2;
	fin>>n>>m;
	build(1, 1, n);
	for(int i=1;i<=m;i+=1)
	{
        fin>>v1>>v2;
        fout<<query(1,1,n,v1,v2).C<<'\n';
	}
	return 0;
}

void build(int n, int l, int r)
{
	if (l == r)
	{
	    int aux;
	    fin>>aux;
		Ar[n].S = Ar[n].D = Ar[n].C = aux;
		Ar[n].Sum = aux;
	}
	else
	{
	    int leftNode=n<<1,rightNode=n<<1|1,middle=(l+r)>>1;

		build(leftNode, l, middle);
		build(rightNode, middle+1, r);

		Ar[n].C = max(max(Ar[leftNode].C, Ar[rightNode].C), Ar[leftNode].D+Ar[rightNode].S);
		Ar[n].D = max(Ar[leftNode].D+Ar[rightNode].Sum, Ar[rightNode].D);
		Ar[n].S = max(Ar[leftNode].S, Ar[leftNode].Sum + Ar[rightNode].S );
		Ar[n].Sum = Ar[leftNode].Sum+Ar[rightNode].Sum;
	}
}

Arb query(int n, int l, int r, int a, int b)
{
	if (a <= l && r <= b) return Ar[n];
	else
    {
        int leftNode=n<<1,rightNode=n<<1|1,middle=(l+r)>>1;

        if(b<=middle) return query(leftNode,l,middle,a,b);
        else if(a>middle) return query(rightNode,middle+1,r,a,b);
        else
        {
            Arb leftInterval = query(leftNode,l,middle,a,b);
            Arb rightInterval = query(rightNode,middle+1,r,a,b);
            Arb aux;
            aux.C = max(max(leftInterval.C, rightInterval.C), leftInterval.D+rightInterval.S);
            aux.S = max(leftInterval.Sum+rightInterval.S, leftInterval.S);
            aux.D = max(rightInterval.Sum+leftInterval.D, rightInterval.D);
            aux.Sum = leftInterval.Sum+rightInterval.Sum;

            return aux;
        }
	}
}