#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define MOD 1000000007
using namespace std;

const int INF = (1 << 30), NMAX(100005);
using VI  = vector<int>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using Point = array<int, 2>;

void BUNA(const string& task = "")
{
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
                freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PA()
{
    exit(0);
}

typedef long long ll;
struct Smecherie
{
    ll sum, pref, suf, rez;
} Arb[4 * NMAX + 5], nmc;

Smecherie uneste(Smecherie a, Smecherie b)
{
    Smecherie rez;
    rez.sum = a.sum + b.sum;
    rez.rez = max(a.rez, max(b.rez, a.suf + b.pref));
    rez.pref = max(a.pref, a.sum + b.pref);
    rez.suf = max(b.suf, b.sum + a.suf);
    return rez;
}

int v[NMAX];

void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        Arb[nod].sum = v[st];
        Arb[nod].pref = v[st];
        Arb[nod].suf = v[st];
        Arb[nod].rez = v[st];
        return;
    }
    int mij = (st + dr) / 2;
    build(2 * nod, st, mij);
    build(2 * nod + 1, mij + 1, dr);

    Arb[nod] = uneste(Arb[2 * nod], Arb[2 * nod + 1]);
}

Smecherie query(int nod, int a, int b, int st, int dr)
{
    if(a > dr || b < st)
        return nmc;
    if(a <= st && dr <= b)
        return Arb[nod];
    int mij = (st + dr) / 2;
    return uneste(query(2 * nod, a, b, st, mij), query(2 * nod + 1, a, b, mij + 1, dr));
}


int main()
{
    BUNA("sequencequery");
    int n, m;
    cin >> n >> m;

    for(int i = 1; i <= n; ++i)
        cin >> v[i];
    nmc.pref = nmc.suf = nmc.sum = nmc.rez = -(1 << 30);
    build(1, 1, n);

    for(int i = 1; i <= m; ++i)
    {
        int st, dr;
        cin >> st >> dr;

        cout << query(1, st, dr, 1, n).rez << '\n';
    }
    PA();
}