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

using namespace std;

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

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

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

void baga(long long nod,long long st,long long dr)
{
     if(st==dr)
     {
          arb1[nod]=arb2[nod]=arb3[nod]=arb4[nod]=sir[st];
          return ;
     }
     long long mij=(st+dr)/2;
     long long stanga=nod*2;
     long long 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(long long nod,long long st,long long 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 ;
     }
     long long mij=(st+dr)/2;
     long long stanga=2*nod;
     long long dreapta=2*nod+1;
     if(start<=mij)
          query(stanga,st,mij);
     if(finish>mij)
          query(dreapta,mij+1,dr);
}

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

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