#include <fstream>
#include <vector>
#include <limits>
using namespace std;

ifstream is("sequencequery.in");
ofstream os("sequencequery.out");

struct Arb{
    long long SumMin, SumMax, Answ;
};

vector<Arb> A;
int n, st, dr, m;
vector<long long> V;
long long fAnsw, sMin;

void Update(int l, int r, int node);
void Query(int l, int r, int node);
void Read();

int main()
{
    Read();
    Update(1, n, 1);
    for ( int i = 1; i <= m; ++i )
    {
        is >> st >> dr;
        fAnsw = numeric_limits<long long>::min();
        sMin = numeric_limits<long long>::max();
        Query(1, n, 1);
        os << fAnsw << '\n';

    }
    is.close();
    os.close();
    return 0;
}

void Update(int l, int r, int node)
{
    if ( l == r )
    {
        A[node].Answ = V[l] - V[l - 1];
        A[node].SumMin = V[l - 1];
        A[node].SumMax = V[l];
        return;
    }
    int mid = (l + r) / 2;
    Update(l, mid, 2 * node);
    Update(mid + 1, r, 2 * node + 1);

    A[node].Answ = max(A[2 * node].Answ, A[2 * node + 1].Answ);
    A[node].Answ = max(A[node].Answ, A[2 * node + 1].SumMax - A[2 * node].SumMin);
    A[node].SumMin = min(A[2 * node].SumMin, A[2 * node + 1].SumMin);
    A[node].SumMax = max(A[2 * node].SumMax, A[2 * node + 1].SumMax);
}

void Query(int l, int r, int node)
{
    if ( st <= l && r <= dr )
    {
        fAnsw = max(max(A[node].Answ, A[node].SumMax - sMin), fAnsw);
        sMin = min(sMin, A[node].SumMin);
        return;
    }

    int mid = (l + r) / 2;
    if ( st <= mid )
        Query(l, mid, 2 * node);
    if ( dr > mid )
        Query(mid + 1, r, 2 * node + 1);
}

void Read()
{
    is >> n >> m;
    A = vector<Arb>(4 * n + 10);
    V = vector<long long>(n + 1);
    for ( int i = 1; i <= n; ++i )
    {
        is >> V[i];
        V[i] += V[i - 1];
    }
}