#include <iostream>
#include <fstream>
#define nl '\n'

using namespace std;

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

const int NMAX = 1e5+5;

int n, v[NMAX];

struct nod
{
    long long int sumaTotala;
    long long int sumaMax;
    long long int bestPref;
    long long int bestSuf;
};
nod aint[4*NMAX];

void build(int node, int low, int high)
{
    if (low == high)
        aint[node].sumaMax = aint[node].bestPref = aint[node].bestSuf = aint[node].sumaTotala = v[low];
    else
    {
        int mid = (low+high)>>1;
        build(2*node, low, mid);
        build(2*node+1, mid+1, high);
        aint[node].sumaTotala = aint[2*node].sumaTotala+aint[2*node+1].sumaTotala;
        aint[node].sumaMax = max(aint[2*node].sumaMax, aint[2*node+1].sumaMax);
        aint[node].sumaMax = max(aint[node].sumaMax, aint[2*node].bestSuf+aint[2*node+1].bestPref);
        aint[node].bestPref = max(aint[2*node].bestPref, aint[2*node].sumaTotala+aint[2*node+1].bestPref);
        aint[node].bestSuf = max(aint[2*node].bestSuf+aint[2*node+1].sumaTotala, aint[2*node+1].bestSuf);
    }
}

nod combine(nod t1, nod t2)
{
    nod result;
    result.sumaTotala = t1.sumaTotala+t2.sumaTotala;
    result.sumaMax = max(t1.sumaMax, t2.sumaMax);
    result.sumaMax = max(result.sumaMax, t1.bestSuf+t2.bestPref);
    result.bestPref = max(t1.bestPref, t1.sumaTotala+t2.bestPref);
    result.bestSuf = max(t1.bestSuf+t2.sumaTotala, t2.bestSuf);
    return result;
}

nod query(int node, int low, int high, int a, int b)
{
    if (a <= low && high <= b)
        return aint[node];
    int mid = (low+high)>>1;
    if (a <= mid && mid+1 <= b)
        return combine(query(2*node, low, mid, a, b), query(2*node+1, mid+1, high, a, b));
    else if (a <= mid)
        return query(2*node, low, mid, a, b);
    else
        return query(2*node+1, mid+1, high, a, b);
}

int main()
{
    int t;
    fin >> n >> t;
    for (int i = 1; i <= n; i++)
        fin >> v[i];
    build(1, 1, n);
    while (t--)
    {
        int x, y;
        fin >> x >> y;
        nod aux = query(1, 1, n, x, y);
        fout << aux.sumaMax << nl;
    }
    return 0;
}