#include <iostream>
#include <fstream>

#define nMax 100000

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

int n, m, v[nMax], x, y, maxim, currSum, start, stop;

int main()
{
    fin>>n>>m;

    for(int i=0;i<n;i++)
        fin>>v[i];

    for(int i=1;i<=m;i++){
      fin>>x>>y;
      x--;
      y--;
      maxim = v[x];
      currSum = maxim;
      start = x;
      stop = x;
      for(int j=x+1;j<=y;j++){
        if (currSum < 0){
            currSum = v[j];
            start = j;
        }
        else
            currSum += v[j];
        if (currSum > maxim){
            maxim = currSum;
            stop = j;
            }
        }
      fout<<maxim<<'\n';
    }


    return 0;
}