#include <stdio.h>
#define MaxN 100100
#define Lim 40
 
int n, m, poz;
int a[MaxN];
long long sum[MaxN];
char buf[20*MaxN];
 
void query(int st, int fn)
{
     int i, j;
     long long s=0, scad=0, best=a[st];
     int last=st+Lim;
     if (last>fn) last=fn;
     for (i=st; i<last; i++){
         s+=a[i];        
         if (s-scad>best) best=s-scad;
         if (s<scad) s=scad;
     }
     int prim=fn-Lim;
     if (last>prim) prim=last;
     if (prim>last) s+=sum[prim-1]-sum[last-1];
     for (i=prim; i<fn; i++){
         s+=a[i];
         if (s-scad>best) best=s-scad;
     }
     printf("%lld\n", best);
}
 
void cit(int &x)
{
     while (buf[poz]<'0' && buf[poz] != '-') poz++;
     int neg = (buf[poz]=='-');
     if (neg) poz++;
     x=0;
     while (buf[poz]>='0') x=x*10+buf[poz++]-'0';
     if (neg) x=-x;
}
 
int main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    fread(buf, 1, sizeof(buf), stdin);
    cit(n); cit(m);
    int i,j,k;
    for (i=0; i<n; i++) cit(a[i]);
    sum[0]=a[0];
    for (i=1; i<n; i++) sum[i]=sum[i-1]+a[i];
    for (i=0; i<m; i++){
        cit(j); cit(k);
        query(j-1, k);
    }
    return 0;
}