#include <iostream>
#include <fstream>
using namespace std;

ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
#define LIMIT 1000080
long long int sum[400900];
long long int v[LIMIT];
 long long int n,m,x,i,y,j,a,b;
 inline long long int kadane(long long int a, long long int b)
 {  long long int max_here=v[a], best_max=v[a],i;
     for(i=a+1;i<=b;i++)
     {  max_here=max(v[i],max_here+v[i]);
     if(max_here>best_max)best_max=max_here;

     }
     return best_max;
 }
 int main()
 {   in>>n>>m;
 for(i=1;i<=n;i++)
    in>>v[i];
 for(j=1;j<=m;j++)
 {
     in>>a>>b;
     out<<kadane(a,b)<<'\n';
 }



    return 0;
}