#include <bits/stdc++.h>

using namespace std;

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

const int nmax = 1e5 + 5e0;

struct node
{
    int pref, secv, suf, val;

    node(int pref = 0, int secv = 0, int suf = 0, int val = 0) : pref(pref), secv(secv), suf(suf), val(val) {}

    void update(int val)
    {
        this->val = val;
        pref = secv = suf = val;
    }

    void updateSecv(int val)
    {
        secv = max(secv, val);
    }

    void updatePref(int val)
    {
        pref = max(pref, val);
    }

    void updateSuf(int val)
    {
        suf = max(suf, val);
    }

} aint[nmax * 3];

int n, q;

void update(int poz, int val, int st = 1, int dr = n, int nod = 1)
{
    if (st == dr)
    {
        aint[nod].update(val);
    }
    else
    {
        int mid = (st + dr) / 2;

        if (poz <= mid)
        {
            update(poz, val, st, mid, nod * 2);
        }
        else
        {
            update(poz, val, mid + 1, dr, nod * 2 + 1);
        }

        aint[nod].val = aint[nod * 2].val + aint[nod * 2 + 1].val;

        aint[nod].secv = max(aint[nod * 2].secv, aint[nod * 2 + 1].secv);
        aint[nod].updateSecv(aint[nod * 2].suf + aint[nod * 2 + 1].pref);

        aint[nod].pref = aint[nod * 2].pref;
        aint[nod].updatePref(aint[nod * 2].val + aint[nod * 2 + 1].pref);

        aint[nod].suf = aint[nod * 2 + 1].suf;
        aint[nod].updateSuf(aint[nod * 2 + 1].val + aint[nod * 2].suf);
    }
}

vector<int> res;

void query(int l, int r, int st = 1, int dr = n, int nod = 1)
{
    if (l == st && r == dr)
    {
        res.push_back(nod);
    }
    else
    {
        int mid = (st + dr) / 2;
        if (r <= mid)
        {
            query(l, r, st, mid, nod * 2);
        }
        else if (l > mid)
        {
            query(l, r, mid + 1, dr, nod * 2 + 1);
        }
        else
        {
            query(l, mid, st, mid, nod * 2);
            query(mid + 1, r, mid + 1, dr, nod * 2 + 1);
        }
    }
}

int minsum(int st, int dr)
{
    int sum = 0;
    for (int i = st + 1; i < dr; i++)
    {
        sum += aint[res[i]].val;
    }
    return aint[res[st]].suf + sum + aint[res[dr]].pref;
}

int main()
{
    in >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        int nr;
        in >> nr;
        update(i, nr);
    }
    for (int i = 0; i < q; i++)
    {
        int a, b;
        in >> a >> b;
        res.clear();
        query(a, b);
        int tmp = aint[res[0]].secv;
        for (int e : res)
        {
            tmp = max(tmp, aint[e].secv);
        }
        for (int i = 0; i < res.size(); i++)
        {
            for (int j = i + 1; j < res.size(); j++)
            {
                tmp = max(tmp, minsum(i, j));
            }
        }
        out << tmp << '\n';
    }
}