#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];
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(arb_int &rez)
{
    rez.total=-inf;
    rez.l=-inf;
    rez.r=-inf;
    rez.sum=-inf;
}
arb_int sum_sub_max(int32_t poz, int32_t st, int32_t dr, int32_t x, int32_t y)
{
    arb_int rez;

    if((x<=st)&&(dr<=y))
    {
        rez=a[poz];
       ///interval inclus in cel cautat
    }
    else if((y<st)||(dr<x))
    {
        init_inf(rez);
        ///nu se intersecteaza
    }
    else
    {
        int32_t mijl=(st+dr)/2, max1, max2;
        arb_int ar1, ar2;

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

        max1=ar1.total;
        max2=ar2.total;

        rez.total=maxim(max1 , maxim(max2 , ar1.r+ar2.l));
        rez.l=maxim(ar1.l , ar1.sum+ ar2.l);
        rez.r=maxim(ar2.r , ar2.sum+ ar1.r);
        rez.sum=ar1.sum+ar2.sum;
    }

     return rez;
}
void intrebari()
{
    int32_t i, x, y;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y;
        arb_int rez=sum_sub_max(1, 1, n, x, y);
        f2<<rez.total<<"\n";
    }
}
int main()
{
    citire();
    creare(1, 1, n);
    intrebari();
    return 0;
}