#include <bits/stdc++.h>
#define NMAX 100005
#define INF 0x3f3f3f3f

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

int N, M;
long long S, rez;
long long inc[4 * NMAX], sfr[4 * NMAX], all[4 * NMAX], sum[4 * NMAX], a[NMAX];

void build(int nod, int st, int dr)
{
    if (st == dr)
    {
        inc[nod] = sfr[nod] = all[nod] = sum[nod] = a[st];
        return;
    }
    int mij = (st + dr) / 2;
    int left = 2 * nod;
    int right = 2 * nod + 1;
    build(left, st, mij);
    build(right, mij + 1, dr);
    sum[nod] = sum[left] + sum[right];
    inc[nod] = max(inc[left], sum[left] + inc[right]);
    sfr[nod] = max(sfr[right], sum[right] + sfr[left]);
    all[nod] = max(sfr[left] + inc[right], max(all[left], all[right]));
}

void query(int nod, int st, int dr, int L, int R)
{
    if (st > R || dr < L)return;
    if (L <= st && dr <= R)
    {
        rez = max(rez, max(all[nod], S + inc[nod]));
        S = max(S + sum[nod], sfr[nod]);
        return;
    }
    int mij = (st + dr) / 2;
    int left = 2 * nod;
    int right = 2 * nod + 1;
    query(left, st, mij, L, R);
    query(right, mij + 1, dr, L, R);
}

int main()
{
    fin >> N >> M;
    for (int i = 1; i <= N; i++)
        fin >> a[i];
    build(1, 1, N);
    for (int i = 1; i <= M; i++)
    {
        int x, y;
        fin >> x >> y;
        rez = -INF;
        S = 0;
        query(1, 1, N, x, y);
        fout << rez << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}