#include <bits/stdc++.h>

//#pragma GCC optimize("Ofast")

using namespace std;

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

const long long INF=1LL*100000*100000+1;

struct seq
{
    long long l, r, sum, best;
    bool operator==(const seq& b) const
    {
        return l==b.l && r==b.r && sum==b.sum && best==b.best;
    }
};

const seq ZERO={-INF, -INF, 0, -INF};

seq t[200000];

seq Merge(const seq& a, const seq& b)
{
    if (a==ZERO)
        return b;
    if (b==ZERO)
        return a;
    return {max(a.l, a.sum+b.l), max(b.r, a.r+b.sum), a.sum+b.sum, max(max(a.best, b.best), a.r+b.l)};
}

long long Query(long long l, long long r, long long n)
{
    seq ans_l, ans_r;
    ans_l=ans_r=ZERO;
    for (l+=n, r+=n;l<r;l/=2, r/=2)
    {   if (l%2)
            ans_l=Merge(ans_l, t[l++]);
        if (r%2)
            ans_r=Merge(t[--r], ans_r);
    }
    return (Merge(ans_l, ans_r)).best;
}

int main()
{
    int n, Q, i, x, l, r;
    fin>>n>>Q;
    for (i=0;i<n;++i)
    {
        fin>>x;
        t[n+i]={x, x, x, x};
    }
    for (i=n-1;i;--i)
        t[i]=Merge(t[i*2], t[i*2+1]);
    while (Q--)
    {
        fin>>l>>r;
        fout<<Query(l-1, r, n)<<'\n';
    }
    fin.close();
    fout.close();

    return 0;
}