#include <fstream>
#include <climits>
using namespace std;

ifstream is("sequencequery.in");
ofstream os("sequencequery.out");

int N,M, x, X, P1, P2, RightSum, MaxSum;
int A, B;
struct T
{
    int a;
    int b;
    int c;
    int d;
};

T Arb[400001];
void Build(int,int,int);
void Query(int,int,int);

int main()
{
    is >> N >> M;
    MaxSum = -99999999999;
    for ( int i = 1; i <= N; ++i )
    {
        is >> x;
        X = i;
        Build(1,1,N);
    }
    for ( int i = 1; i <= M; ++i )
    {
        is >> P1 >> P2;
        RightSum = 0;
            MaxSum = INT_MIN;
        Query(1,1,N);
        os << MaxSum << '\n';
    }

    is.close();
    os.close();
}

void Build(int node, int left, int right)
{
    if ( left == right )
    {
        Arb[node].a = x;
        Arb[node].b = x;
        Arb[node].c = x;
        Arb[node].d = x;
        return;
    }

    int mid = (left+right)/2;

    if ( X <= mid ) Build(node*2,left,mid);
    else    Build(node*2+1,mid+1,right);

    Arb[node].d = Arb[node*2].d + Arb[node*2+1].d;
    Arb[node].a = max(Arb[node*2].a,Arb[node*2+1].a + Arb[node*2].d);
    Arb[node].b = max(Arb[node*2+1].b,Arb[node*2+1].d + Arb[node*2].b);
    Arb[node].c = Arb[node*2+1].a + Arb[node*2].b;
    Arb[node].c = max(Arb[node].c,max(Arb[node*2].c,Arb[node*2+1].c));
}

void Query(int node, int left, int right)
{
    if ( left >= P1 && right <= P2 )
    {
        MaxSum = max(MaxSum,max(RightSum + Arb[node].a,Arb[node].c));
        RightSum = max(Arb[node].d + RightSum,Arb[node].b);
        return;
    }

    int mid = (left+right)/2;

    if ( P1 <= mid )
        Query(node*2,left,mid);
    if ( P2 > mid )
        Query(node*2+1,mid+1,right);
}