#include <bits/stdc++.h>

std::ifstream in("sequencequery.in");
std::ofstream o("sequencequery.out");

int v[100010], maxim[100010],n,m,x,y,suma;

int main()
{
    in>>n>>m;
    for(int i=1; i<=n; i++)
        in>>v[i];
    while(m)
    {
        in>>x>>y;
        suma=v[x];
        maxim[x]=v[x];
        for(int i=x+1; i<=y; i++)
            maxim[i]=-100000;
        for(int i=x+1; i<=y; i++)
        {
            if(v[i]>maxim[i-1]+v[i])
                maxim[i]=v[i];
            else
                maxim[i]=maxim[i-1]+v[i];
            if(maxim[i]>suma)
                suma=maxim[i];
        }
        o<<suma<<"\n";
        m--;
    }
}