#include <fstream>

using namespace std;

ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
int n, a[100001];
void subsecv_max(int st, int dr)
{
    int s=0, smax=-((1<<31)-1);
    for(int i=st;i<=dr;++i)
        {
            if(s+a[i]>=a[i])
                s+=a[i];
            else s=a[i];
            if(smax<s)
                smax=s;
        }
    cout<<smax<<"\n";
}
int main()
{
    int i, m,inceput, sfarsit;
    cin>>n>>m;
    for(i=1;i<=n;++i)
        cin>>a[i];
    for(i=1;i<=m;i++)
        cin>>inceput>>sfarsit, subsecv_max(inceput, sfarsit);
    cin.close();
    cout.close();
    return 0;
}