#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++)
            maxim[i]=std::max(v[i],maxim[i-1]+v[i]);
        for(int i=x;i<=y;i++)
            suma=std::max(suma,maxim[i]);
        o<<suma<<"\n";
        m--;
    }
}