#include <fstream>

using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
int a[100001],n,m,i,j,x,y;
long long MAX,sum;
int main()
{
   f>>n>>m;
   for (i=1;i<=n;i++)
    f>>a[i];
   for (i=1;i<=m;i++)
   {
       f>>x>>y;
       MAX=-100001;
       sum=0;
       for (j=x;j<=y;j++)
        {if (sum+a[j]>a[j])
        sum=sum+a[j];
       else sum=a[j];
       MAX=max(MAX,sum);
       }
       g<<MAX<<'\n';
   }
    return 0;
}