#include <iostream>
#include <fstream>
#include <algorithm>

#define fiu1 (nod << 1)
#define fiu2 (fiu1 + 1)
#define mid ((st + dr) >> 1)

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

const int Nmax = 100010;
const int oo = 0x3f3f3f3f;

struct nod{
    long long a, b, c, sum;
    nod(){a = b = c = sum = 0;}
}arb[Nmax * 3 + 100];

long long N, M, poz, val, maxim, sum;

void Update(int nod, int st, int dr)
{
    if(st == dr)
    {
        arb[nod].a = arb[nod].b = arb[nod].c = arb[nod].sum = val;
        return;
    }

    if(poz <= mid) Update(fiu1, st, mid);
    else Update(fiu2, mid + 1, dr);

    arb[nod].sum = arb[fiu1].sum + arb[fiu2].sum;
    arb[nod].a = max(arb[fiu1].a, arb[fiu1].sum + arb[fiu2].a);
    arb[nod].b = max(arb[fiu2].b, arb[fiu2].sum + arb[fiu1].b);
    arb[nod].c = max(max(arb[fiu1].c, arb[fiu2].c), arb[fiu1].b + arb[fiu2].a);
}

void Query(int nod, int st, int dr, int left, int right)
{
    if(st > right || dr < left) return;

    if(left <= st && dr <= right)
    {
        maxim = max(max(arb[nod].a + sum, arb[nod].c), maxim);
        sum = max(sum + arb[nod].sum, arb[nod].b);
        return;
    }

    Query(fiu1, st, mid, left, right);
    Query(fiu2, mid + 1, dr, left, right);
}

int main()
{
    fin>>N>>M;
    for(int i=1; i<=N; i++)
    {
        fin>>val; poz = i;
        Update(1, 1, N);
    }

    for(int x, y; M; M--)
    {
        fin>>x>>y;
        maxim = -oo, sum = 0;
        Query(1, 1, N, x, y);
        fout<<maxim<<'\n';
    }
    return 0;
}