#include <fstream>

using namespace std;

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

const int NMAX = 100000 + 5;

int N, M;

struct Node{
    long long sumTotal;

    long long sumMax;
    long long prefMax, sufMax;
};

struct Aint{

    Node v[4 * NMAX];

    Node Merge(Node A, Node B)
    {
        Node ans;

        ans.sumTotal = A.sumTotal + B.sumTotal;
        ans.sumMax = max(A.sufMax + B.prefMax, max(A.sumMax, B.sumMax));
        ans.prefMax = max(A.prefMax, A.sumTotal + B.prefMax);
        ans.sufMax = max(B.sufMax, B.sumTotal + A.sufMax);

        return ans;
    }

    void Update(int node, int st, int dr, int pos, int val)
    {
        if(st == dr)
        {
            v[node].sumTotal = v[node].sumMax = v[node].prefMax = v[node].sufMax = val;
            return ;
        }

        int mid = (st + dr) / 2;

        if(pos <= mid)
            Update(2 * node, st, mid, pos, val);
        else
            Update(2 * node + 1, mid + 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(l == st && r == dr)
            return v[node];

        int mid = (st + dr) >> 1;

        if(r <= mid)
            return Query(2 * node, st, mid, l, r);

        if(l > mid)
            return Query(2 * node + 1, mid + 1, dr, l, r);

        return Merge(Query(2 * node, st, mid, l, mid), Query(2 * node + 1, mid + 1, dr, mid + 1, r));
    }

};

Aint aint;

int main()
{
    int x, y;

    fin >> N >> M;

    for(int i = 1; i <= N; i++)
    {
        fin >> x;
        aint.Update(1, 1, N, i, x);
    }

    for(int i = 1; i <= M; i++)
    {
        fin >> x >> y;
        fout << aint.Query(1, 1, N, x, y).sumMax << '\n';
    }

    return 0;
}