#include<iostream>
#include<fstream>
#include<limits.h>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int a[100001];
int maxim(int a,int b)
{
    if (a>b)
        return a;
    else if (b>a)
        return b;
}
int main ()
{
    int n,m;
    fin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        fin>>a[i];
    }
    while (m!=0)
    {
        m--;
        int x,y;
        fin>>x>>y;
        int maxim2=-INT_MAX;
        int best[100001];
        for (int i=x-1;i<=y+1;i++)
        {
            best[i]=0;
        }
        for (int i=x;i<=y;i++)
        {
            best[i]=maxim(best[i-1]+a[i],a[i]);
            if (best[i]>maxim2)
                maxim2=best[i];
        }
        fout<<maxim2<<"\n";
    }
}