#include <iostream>
#include <fstream>

using namespace std;

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

struct nod
{
    int max,min,val;
}a[1000000];

int v[111111],rez,ming;

inline int maxim(int a,int b)
{
    if(a>b)
        return a;
    return b;
}

inline int minim(int a,int b)
{
    if(a>b)
        return b;
    return a;
}

void completeaza(int poz,int left,int right,int p)
{
    int mid=(right+left)/2;
    if(p==left && p==right)
    {
        a[poz].min=minim(v[p-1],v[p]);
        a[poz].max=v[p];
        a[poz].val=v[p]-v[p-1];
        return;
    }
    if(p<=mid)
        completeaza(2*poz,left,mid,p);
    else
        completeaza(2*poz+1,mid+1,right,p);
    a[poz].min=minim(a[2*poz].min,a[2*poz+1].min);
    a[poz].max=maxim(a[2*poz].max,a[2*poz+1].max);
    a[poz].val=maxim(maxim(a[2*poz].val,a[2*poz+1].val),a[2*poz+1].max-a[2*poz].min);
}

void query(int poz,int left,int right,int p,int q)
{
    int mid=(right+left)/2;
    if(p<=left && right<=q)
    {
        rez=maxim(maxim(rez,a[poz].val),a[poz].max-ming);
        ming=minim(ming,a[poz].min);
        return;
    }
    if(p<=mid)
        query(2*poz,left,mid,p,q);
    if(mid<q)
        query(2*poz+1,mid+1,right,p,q);
}

int main()
{
    int n,p,i,c,poz,m,st,dr;
    in>>n>>p;
    for(i=1;i<=n;++i)
    {
        in>>v[i];
        v[i]+=v[i-1];
        completeaza(1,1,n,i);
    }
    for(i=1;i<=p;++i)
    {
        in>>st>>dr;
        rez=-1000000000;
        ming=1000000000;
        query(1,1,n,st,dr);
        out<<rez<<"\n";
    }
    return 0;
}