#include <stdio.h>
#define maxn 100010*5

using namespace std;

int arb1[maxn],arb2[maxn],arb3[maxn],arb4[maxn];

int n,m,sir[maxn];
int start,finish,sum,max;

int maxim(int a,int b)
{
     return a>b?a:b;
}

void baga(int nod,int st,int dr)
{
     if(st==dr)
     {
          arb1[nod]=arb2[nod]=arb3[nod]=arb4[nod]=sir[st];
          return ;
     }
     int mij=(st+dr)/2;
     int stanga=nod*2;
     int dreapta=2*nod+1;
     baga(stanga,st,mij);
     baga(dreapta,mij+1,dr);
     arb1[nod]=maxim(arb1[stanga],arb4[stanga]+arb1[dreapta]);
     arb2[nod]=maxim(arb2[dreapta],arb4[dreapta]+arb2[stanga]);
     arb3[nod]=maxim(arb3[dreapta],arb3[stanga]);
     arb3[nod]=maxim(arb3[nod],arb1[dreapta]+arb2[stanga]);
     arb4[nod]=arb4[dreapta]+arb4[stanga];
}

void query(int nod,int st,int dr)
{
     if(st>=start && finish>=dr)
     {
          if (sum<0)
               sum=0;
          max=maxim(max,sum+arb1[nod]);
          max=maxim(max,arb3[nod]);
          sum=maxim(sum+arb4[nod],arb2[nod]);
          return ;
     }
     int mij=(st+dr)/2;
     int stanga=2*nod;
     int dreapta=2*nod+1;
     if(start<=mij)
          query(stanga,st,mij);
     if(finish>mij)
          query(dreapta,mij+1,dr);
}

void solve()
{
     for (int i=0;i<m;i++)
     {
          scanf("%d%d\n",&start,&finish);
          sum=0;
          max=-200000;
          query(1,1,n);
          printf("%d\n",max);
     }
}

int main ()
{
     freopen("sequencequery.in","r",stdin);
     freopen("sequencequery.out","w",stdout);
     scanf("%d%d",&n,&m);
     for(int i=1;i<=n;i++)
          scanf("%d",&sir[i]);
     baga(1,1,n);
     solve();
     return 0;
}