#include <fstream>
#include <stdint.h>
#define nmax 100001
using namespace std;
fstream f1("sequencequery.in", ios::in);
fstream f2("sequencequery.out", ios::out);
int32_t n, m, v[nmax];
struct arb_int
{
    int32_t total, l, r, sum;
}a[4*nmax], aux[4*nmax];
const int32_t inf=1000000000;
///n= nr valori
///v= vect de valori
///m= nr intrebari
///a[poz].total= suma maxima a unei subsecvente de pe intervalul coresp lui poz;
///a[poz].l=suma maxima a unei subsecvente care incepe cu primul element de pe intervalul coresp lui poz;
///a[poz].r=suma maxima a unei subsecvente care se termina cu ultimul element de pe intervalul coresp lui poz;
///a[poz].sum=suma tuturor valorilor de pe intervalul coresp lui poz;
void citire()
{
    int32_t i;
    f1>>n>>m;
    for(i=1; i<=n; i++)
        f1>>v[i];
}
void init (int32_t poz)
{
    a[poz].total=0;
    a[poz].l=0;
    a[poz].r=0;
    a[poz].sum=0;
}
int32_t maxim(int32_t a, int32_t b)
{
    if(a>b) return a;
    else return b;
}
void creare(int32_t poz, int32_t st ,int32_t dr)
{
    if(st<dr)
    {
      int32_t mijl=(st+dr)/2;
      init(2*poz);
      init(2*poz+1);
      creare(poz*2, st, mijl);
      creare(poz*2+1, mijl+1, dr);

      a[poz].total= maxim(a[poz*2].total, maxim( a[poz*2+1].total, a[poz*2].r+a[poz*2+1].l));
      a[poz].l=maxim(a[poz*2].l, a[poz*2].sum+a[poz*2+1].l);
      a[poz].r=maxim(a[poz*2+1].r, a[poz*2+1].sum+ a[poz*2].r);
      a[poz].sum= a[poz*2].sum+a[poz*2+1].sum;
    }
    else if(st==dr)
    {
        a[poz].total=v[st];
        a[poz].l=v[st];
        a[poz].r=v[st];
        a[poz].sum=v[st];
    }
}
void init_inf(int32_t poz)
{
    aux[poz].total=-inf;
    aux[poz].l=-inf;
    aux[poz].r=-inf;
    aux[poz].sum=-inf;
}
int32_t sum_sub_max(int32_t poz, int32_t st, int32_t dr, int32_t x, int32_t y)
{
    if((x<=st)&&(dr<=y))
    {
        aux[poz]=a[poz];
       ///interval inclus in cel cautat
    }
    else if((y<st)||(dr<x))
    {
       init_inf(poz);
        ///nu se intersecteaza
    }
    else
    {
        int32_t mijl=(st+dr)/2, max1=-inf, max2=-inf;

        if(x<=mijl) max1=sum_sub_max(2*poz, st, mijl, x, y);
        else init_inf(2*poz);
        if(mijl<y)  max2=sum_sub_max(2*poz+1, mijl+1, dr, x, y);
        else init_inf(2*poz+1);

        aux[poz].total=maxim(max1 , maxim(max2 , aux[2*poz].r+aux[2*poz+1].l));
        aux[poz].l=maxim(aux[poz*2].l , aux[poz*2].sum+ aux[poz*2+1].r);
        aux[poz].r=maxim(aux[poz*2+1].r , aux[poz*2+1].sum+ aux[poz*2].r);
        aux[poz].sum=aux[poz*2].sum+aux[poz*2+1].sum;
    }
     return aux[poz].total;
}
void intrebari()
{
    int32_t i, x, y;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y;
        f2<<sum_sub_max(1, 1, n, x, y)<<"\n";
    }
}
int main()
{
    citire();
    creare(1, 1, n);
    intrebari();
    return 0;
}