#include <bits/stdc++.h>
#define INF LLONG_MAX / 2
#define ll long long
#define DIM 100005

using namespace std;

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

struct elem
{
    ll maxi, mini, best;
}aint[4 * DIM];

int n, q;
ll a[DIM], prefixMin;

void Build(int nod, int st, int dr)
{
    if(st == dr)
    {
        aint[nod] = {a[st], a[st], a[st] - a[st - 1]};
        return ;
    }
    int mid = (st + dr) / 2;
    Build(2 * nod, st, mid);
    Build(2 * nod + 1, mid + 1, dr);

    aint[nod].best = max(aint[2 * nod].best, max(aint[2 * nod + 1].best, aint[2 * nod + 1].maxi - aint[2 * nod].mini));
    aint[nod].maxi = max(aint[2 * nod].maxi, aint[2 * nod + 1].maxi);
    aint[nod].mini = min(aint[2 * nod].mini, aint[2 * nod + 1].mini);
}

ll Query(int nod, int st, int dr, int stQ, int drQ)
{
    if(stQ <= st && dr <= drQ)
    {
        ll ans = aint[nod].best;
        if(prefixMin != INF)
            ans = max(ans, aint[nod].maxi - prefixMin);

        prefixMin = min(prefixMin, aint[nod].mini);
        //g << aint[nod].maxi << " " << prefixMin << "\n";
        return ans;
    }

    int mid = (st + dr) / 2;
    if(mid < drQ && mid >= stQ)
    {
        int x = Query(2 * nod, st, mid, stQ, drQ);
        int y = Query(2 * nod + 1, mid + 1, dr, stQ, drQ);
        return max(x, y);
    }
    else if(mid < stQ)
        return Query(2 * nod + 1, mid + 1, dr, stQ, drQ);
    else
        return Query(2 * nod, st, mid, stQ, drQ);
}

int main()
{
    f >> n >> q;
    for(int i = 1; i <= n; i++)
        f >> a[i], a[i] += a[i - 1];

    Build(1, 1, n);

    for(int i = 1; i <= q; i++)
    {
        int x, y;
        f >> x >> y;
        prefixMin = INF;
        g << Query(1, 1, n, x, y) << "\n";
    }

    return 0;
}