#include <cstdio>
#include <algorithm>
#define N 1<<18
#define mid ((l+r)/2)
using namespace std;

long long n,m,v[N],A[N<<1],B[N<<1],C[N<<1],Sum[N<<1],zero;

void Build(long long n,long long l,long long r){

    if (l==r) {
              A[n]=B[n]=C[n]=v[l];
              Sum[n]=v[l];
              }
    else {
          Build(2*n,l,mid);
          Build(2*n+1,mid+1,r);

          A[n] = max(A[2*n], Sum[2*n]+A[2*n+1]);
		  B[n] = max(B[2*n]+Sum[2*n+1], B[2*n+1]);
		  C[n] = max(max(C[2*n], C[2*n+1]), B[2*n]+A[2*n+1]);

		  Sum[n]=Sum[2*n]+Sum[2*n+1];
         }
}

long long a,b;
long long S,sol;

void Query(long long n,long long l,long long r){

    if (a<=l && r<=b) {
                       sol=max(sol, max(S+A[n], C[n]));
                       S=max(S+Sum[n], B[n]);
                      }
    else {
          if (a<=mid) Query(2*n,l,mid);
          if (b>mid) Query(2*n+1,mid+1,r);
         }
}

int main()
{
    long long i,op,n1,n2;
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);

    scanf("%lld%lld",&n,&m);
    for (i=1;i<=n;++i)
        scanf("%lld",&v[i]);

    Build(1,1,n);

    while (m--){
        scanf("%lld%lld",&n1,&n2);
        S=sol=-100000;
        a=n1;
        b=n2;
        Query(1,1,n);
        printf("%lld\n",sol);
        }

    return 0;
}