#include <fstream.h>
int *T=new int[100000];
int *x=new int[100000];
int *y=new int[100000];
int *summx=new int[100000];
unsigned int n, m, i, j;
long sumamax, sumac, sfarsit, inceput, pozincep; 
int main()
{
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
f>>n>>m;
for(i=1; i<=n; i++)
    f>>T[i];
for(i=1; i<=m; i++)
    {f>>x[i]>>y[i];}
for(i=1; i<=m; 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;
      }
    }
   summx[i]=sumamax;
   }
for(i=1; i<=m; i++)
   g<<summx[i]<<"\n";
f.close();
g.close();
return 0;
}