#include <cstdio>

using namespace std;
int n,m,a[100003],x,y,i,j,sc,smax;
int main()
{freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=m;i++){
scanf("%d %d",&x,&y);
sc=a[x];smax=a[x];
for(j=x+1;j<=y;j++){
if(sc+a[j]<a[j])sc=a[j];
else sc+=a[j];
if(sc>smax)smax=sc;
}
printf("%d\n",smax);
}

    return 0;
}