#include <fstream>

#define LL long long

using namespace std;

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

const long long inf = 1000000000;
int n, m, a, b;
long long minim_prefix, val, S[100010];
struct { long long amin, amax, abest; } AI[100010];

inline LL Minim(const LL &x, const LL &y)
{
    if (x < y) return x;
    return y;
}

inline LL Maxim(const LL &x, const LL &y)
{
    if (x > y) return x;
    return y;
}

void Build_Tree(int nod, int left, int right)
{
    if (left == right)
    {
        AI[nod] = { S[left], S[left], S[left] - S[left - 1] };
        return;
    }
    AI[nod] = { inf, -inf, -inf };
    int mid = (left + right) / 2;
    Build_Tree(nod * 2, left, mid);
    Build_Tree(nod * 2 + 1, mid + 1, right);
    AI[nod].amin = Minim(AI[nod * 2].amin, AI[nod * 2 + 1].amin);
    AI[nod].amax = Maxim(AI[nod * 2].amax, AI[nod * 2 + 1].amax);
    AI[nod].abest = Maxim(AI[nod * 2].abest, Maxim(AI[nod * 2 + 1].abest, AI[nod * 2 + 1].amax - AI[nod * 2].amin));
}

long long Query(int nod, int left, int right)
{
    if (a <= left && right <= b)
    {
        long long ret = Maxim(AI[nod].abest, AI[nod].amax - minim_prefix);
        minim_prefix = Minim(minim_prefix, AI[nod].amin);
        return ret;
    }
    int mid = (left + right) / 2;
    if (a <= mid && mid < b)
    {
        long long ret1 = Query(nod * 2, left, mid); // asta primul pt minim_prefix
        long long ret2 = Query(nod * 2 + 1, mid + 1, right);
        return Maxim(ret1, ret2);
    }
    else if (mid < a)
    {
        return Query(nod * 2 + 1, mid + 1, right);
    }
    else
    {
        return Query(nod * 2, left, mid);
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        fin >> val;
        S[i] = S[i - 1] + val;
    }
    Build_Tree(1, 1, n);
    for (int i = 1; i <= m; i ++)
    {
        fin >> a >> b;
        minim_prefix = inf;
        fout << Query(1, 1, n) << '\n';
    }
    fout.close();
    return 0;
}