//#include <fstream.h>
#include <stdio.h>
int *T=new int[100000];
int *x=new int[100000];
int *y=new int[100000];
unsigned int n, m, i, j;
long sumamax, sumac, sfarsit, inceput, pozincep;
int main()
{
freopen("sequencequery.in", "r", stdin);
freopen("sequencequery.out", "w", stdout);
//f>>n>>m;
scanf("%u %u", &n, &m);
for(i=1; i<=n; ++i)
    //f>>T[i];
    scanf("%d", &T[i]);
for(i=1; i<=m; ++i)
    {//f>>x[i]>>y[i];
     scanf("%d %d", &x[i], &y[i]);
   sumamax=T[x[i]];
   sumac=sumamax;
   pozincep=x[i];
   sfarsit=x[i];
   for(j=x[i]+1; j<=y[i]; ++j)
       {if(sumac<0)
       {sumac=T[j];
	pozincep=j;
       }
     else
       sumac+=T[j];
    if(sumac>sumamax)
      {sumamax=sumac;
       inceput=pozincep;
       sfarsit=j;
      }
    }
   //g<<sumamax<<'\n';
   printf("%l \n", sumamax);
   }
//f.close();
//g.close();
return 0;
}