#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <climits>

using namespace std;

int n, m;

int v[100003];

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

int kadane(int st,int dr)
{
    int sum=v[st];
    int maxim=v[st];
    for(int i=st+1; i<=dr; i++)
    {
        if(sum+v[i]<v[i])
        {
            sum=v[i];
        }
        else{
            sum+=v[i];
        }
        maxim=max(sum,maxim);
    }
    return maxim;
}

int main()

{

    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;
        fout<<kadane(st,dr)<<"\n";
    }
    return 0;
}