#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]=-INT_MAX;
        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];
        for(int i=x;i<=y;i++)
            if(maxim[i]>suma)
                suma=maxim[i];
        o<<suma<<"\n";
        m--;
    }
}