#include <fstream>
#include <iostream>
#define MAX (1<<18)
#define ns (nod<<1)
#define nd (ns+1)
#define m ((st+dr)>>1)
#define maxi(a, b) ((a) > (b) ? (a) : (b))

using namespace std;

int n, a, b;
long long sum, rez, val[MAX];
long long L[MAX<<1], R[MAX<<1], S[MAX<<1], C[MAX<<1];

void Build(int nod, int st, int dr)
{
     if (st == dr)     
     {
         L[nod] = R[nod] = S[nod] = C[nod] = val[st];
         return;       
     }
     
     Build(ns, st,  m);
     Build(nd, m+1, dr);
     
     S[nod] = S[ns] + S[nd];
     L[nod] = maxi(S[ns] + L[nd], L[ns]);
     R[nod] = maxi(S[nd] + R[ns], R[nd]);
     C[nod] = maxi(maxi(C[ns], C[nd]), R[ns] + L[nd]);
}

void Query(int nod, int st, int dr)
{
     if (a <= st && dr <= b)     
     {
         rez = maxi(rez, maxi(sum + L[nod], C[nod]));      
         sum = maxi(sum + S[nod], R[nod]);
         return;
     }
     
     if (a <= m) Query(ns, st,  m);
     if (m < b)  Query(nd, m+1, dr);
}

int main()
{
    int i, q;
    
    ifstream fin("sequencequery.in");
    ofstream fout("sequencequery.out");
    
    fin >> n >> q;
    for (i = 1; i <= n; i++)
        fin >> val[i];
    Build(1, 1, n);
    
    for (i = 1; i <= q; i++)
    {
        fin >> a >> b;
        rez = -9999999;
        sum = 0;
        Query(1, 1, n);    
        fout << rez << "\n";
    }
    
    fin.close();
    fout.close();
    
    return 0;
}