#include <iostream>
#include <fstream>
using namespace std;
const int Nmax = 100005;
struct node
{
long long totalSum;
long long bestPreffix;
long long bestSuffix;
long long bestSum;
};
node Arb[4 * Nmax];
void update( int nod, int st, int dr, int val, int pos )
{
if ( st == dr )
{
Arb[nod].totalSum = val;
Arb[nod].bestPreffix = val;
Arb[nod].bestSuffix = val;
Arb[nod].bestSum = val;
}
else
{
int m = ( st + dr ) / 2;
if ( pos <= m )
update( 2 * nod, st, m, val, pos );
else
update( 2 * nod + 1, m + 1, dr, val, pos );
Arb[nod].totalSum = Arb[2 * nod].totalSum + Arb[2 * nod + 1].totalSum;
Arb[nod].bestPreffix = max( Arb[2 * nod].bestPreffix, Arb[2 * nod].totalSum + Arb[2 * nod + 1].bestPreffix );
Arb[nod].bestSuffix = max( Arb[2 * nod + 1].bestSuffix, Arb[2 * nod + 1].totalSum + Arb[2 * nod].bestSuffix );
Arb[nod].bestSum = max( Arb[2 * nod].bestSum, Arb[2 * nod + 1].bestSum );
Arb[nod].bestSum = max( Arb[nod].bestSum, Arb[2 * nod].bestSuffix + Arb[2 * nod + 1].bestPreffix );
}
}
node query( int nod, int st, int dr, int start, int finish )
{
if ( start <= st && dr <= finish )
{
return Arb[nod];
}
else
{
int m = ( st + dr ) / 2;
int lf = 0, rt = 0;
node lft, rgt;
if ( start <= m )
{
lf = 1;
lft = query( 2 * nod, st, m, start, finish );
}
if ( m < finish )
{
rt = 1;
rgt = query( 2 * nod + 1, m + 1, dr, start, finish );
}
if ( lf + rt != 2 )
{
if ( lf )
return lft;
else
return rgt;
}
else
{
node temp;
temp.totalSum = lft.totalSum + rgt.totalSum;
temp.bestPreffix = max( lft.bestPreffix, lft.totalSum + rgt.bestPreffix );
temp.bestSuffix = max( rgt.bestSuffix, rgt.totalSum + lft.bestSuffix );
temp.bestSum = max( max ( lft.bestSum, rgt.bestSum ), lft.bestSuffix + rgt.bestPreffix );
return temp;
}
}
}
int main()
{
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
int N, M;
f >> N >> M;
for ( int i = 1, val; i <= N; ++i )
{
f >> val;
update( 1, 1, N, val, i );
}
for ( int i = 1, x, y; i <= M; ++i )
{
f >> x >> y;
node temp = query( 1, 1, N, x, y );
g << temp.bestSum << "\n";
}
return 0;
}