#include <bits/stdc++.h>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int v[100001];
int main()
{
  int n,m;
  fin>>n>>m;
  for(int i=1;i<=n;i++)
  {
      fin>>v[i];
  }
  for(int i=1;i<=m;i++)
  {
      int st,dr;
      fin>>st>>dr;
      int sum=0,smax=v[st];
      for(int j=st;j<=dr;j++)
      {
          if(sum<0)
          {
              sum=v[j];
          }
          else
            sum+=v[j];
          if(sum>smax)smax=sum;
      }
      fout<<smax<<'\n';
  }
}