#include <stdio.h>
#define MaxN 100100
#define Lim 50

int n, m;
int a[MaxN], sum[MaxN], min[MaxN];

void query(int st, int fn)
{
     int i, j, best=a[st];
     int scad=0, s=0;
     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;
     for (i=prim; i<fn; i++){
         s+=a[i];
         if (s-scad>best) best=s-scad;
     }
     printf("%d\n", best);
}

int main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    scanf("%d %d", &n, &m);
    int i,j,k;
    for (i=0; i<n; i++) scanf("%d", a+i);
    sum[0]=a[0];
    for (i=1; i<n; i++) sum[i]=sum[i-1]+a[i];
    for (i=1; i<n; i++)
        if (sum[i]<min[i-1]) min[i]=sum[i]; else min[i]=min[i-1];
    for (i=0; i<m; i++){
        scanf("%d %d", &j, &k);
        query(j-1, k);
    }
    return 0;
}