#include <bits/stdc++.h>
using namespace std;

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

struct Node
{
    long long left, right, s, ans;
};

struct Aint
{
    Node v[400005];

    Node Merge(Node first, Node second)
    {
        Node ans;

        ans.s = first.s + second.s;
        ans.left = max(first.left, first.s + second.left);
        ans.right = max(second.right, second.s + first.right);
        ans.ans = max(first.right + second.left, max(first.ans, second.ans));
        return ans;
    }


    void update(int node, int st, int dr, int pos, int val)
    {
        if(st == dr)
        {
            v[node].left = v[node].right = v[node].ans = v[node].s = val;
            return;
        }

        int mij = (st + dr) / 2;

        if(pos <= mij)
            update(2*node, st, mij, pos, val);
        else
            update(2*node + 1, mij + 1, dr, pos, val);

        v[node] = Merge(v[2*node], v[2*node + 1]);
    }

    Node query(int node, int st, int dr, int l, int r)
    {
        if(st == l && dr == r)
            return v[node];

        int mij = (st + dr) / 2;

        if(r <= mij)
            return query(2*node, st, mij, l, r);
        else
            if(l >= mij + 1)
            return query(2*node + 1, mij + 1, dr, l, r);
        else
            return Merge(query(2*node, st, mij, l, mij),query(2*node + 1, mij + 1, dr, mij + 1, r));
    }
}aint;

int main()
{
    int n, m;

    fin >> n >> m;

    for(int i = 1; i <= n ; i++)
    {
        int x;
        fin >> x;

        aint.update(1, 1, n, i, x);
    }

    for(int i = 1; i <= m ; i++)
    {
        int x, y;
        fin >> x >> y;

        fout << aint.query(1, 1, n, x, y).ans << '\n';
    }

    return 0;
}