#include <fstream>
#define MAX 100000

using namespace std;

ifstream f("sequencequery.in");
ofstream g("sequencequery.out");

long long n,m,a[1001],sum[1001],max1[4001],min1[4001],aib[4001];

void constructie(int st,int dr,int nod)
{
    if(st==dr)
    {
        max1[nod]=sum[st];
        min1[nod]=sum[st-1];
        aib[nod]=a[st];
        return;
    }
    long long mij=(st+dr)/2;
    constructie(st,mij,nod*2);
    constructie(mij+1,dr,nod*2+1);
    max1[nod]=max(max1[nod*2],max1[nod*2+1]);
    min1[nod]=min(min1[nod*2],min1[nod*2+1]);
    aib[nod]=max(aib[nod*2],aib[nod*2+1]);
    aib[nod]=max(aib[nod],max1[nod*2+1]-min1[nod*2]);
}

long long querry(int st,int dr,int x,int y,int nod,long long &maxx,long long &minn)
{
    if(y<st || x>dr)
    {
        maxx=-MAX;
        minn=MAX;
        return -(MAX*n);
    }
    if(x<=st && y>=dr)
    {
        maxx=max1[nod];
        minn=min1[nod];
        return aib[nod];
    }
    long long mij=(st+dr)/2;
    long long maxim1,minim1,maxim2,minim2;
    long long rez;
    rez=max(querry(st,mij,x,y,nod*2,maxim1,minim1),querry(mij+1,dr,x,y,nod*2+1,maxim2,minim2));
    rez=max(rez,maxim2-minim1);
    maxx=max(maxim1,maxim2);
    minn=min(minim1,minim2);
    return rez;
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    constructie(1,n,1);
    for(int q=1;q<=m;q++)
    {
        int st,dr;
        f>>st>>dr;
        long long bla1,bla2;
        g<<querry(1,n,st,dr,1,bla1,bla2)<<'\n';
    }
    return 0;
}