#include <fstream>
#define MAX 100000
#define ns (2*nod)
#define nd (ns+1)
#define ma(a, b) ((a) > (b) ? (a) : (b))

using namespace std;

int n, val[MAX];
long long S, rez;
struct Node{ 
    long long c, l, r, s;
} a[MAX<<1];   

void Build(int nod, int st, int dr);
void Querry(int nod, int st, int dr, int x, int y);

int main()
{
    int i, q, p, v;
    
    ifstream fin("maxq.in");
    ofstream fout("maxq.out");
    
    fin >> n >> q;
    for (i = 1; i <= n; i++)
        fin >> val[i];
    Build(1, 1, n);
    
    for (i = 1; i <= q; i++)
    {
        fin >> p >> v;
        S = 0;
        rez = -999999;
        Querry(1, 1, n, p, v);
        fout << rez << "\n";
    }
    
    fout.close();
    fin.close();    
    
    return 0;
}

void Build(int nod, int st, int dr)
{
    if (st == dr)
    {
        a[nod].l = a[nod].r = a[nod].c = val[st];
        a[nod].s = val[st];
        return;       
    }     
    
    int m = (st+dr)/2;
    
    Build(ns, st, m);
    Build(nd, m+1, dr);
    
    a[nod].s = a[ns].s + a[nd].s;
    a[nod].l = ma(a[ns].s + a[nd].l, a[ns].l);
    a[nod].r = ma(a[nd].s + a[ns].r, a[nd].r);
    a[nod].c = ma(ma(a[ns].c, a[nd].c), a[ns].r + a[nd].l);
}

void Querry(int nod, int st, int dr, int x, int y)
{
    if (x <= st && dr <= y)      
    {
        rez = ma(rez, ma(S + a[nod].l, a[nod].c));
        S = ma(S + a[nod].s, a[nod].r);
        return;      
    }
    
    int m = (st + dr)/2;
    
    if (x <= m) Querry(ns, st, m, x, y);
    if (m < y)  Querry(nd, m+1, dr, x, y);
}