#include <bits/stdc++.h>
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
int l[200002],r[200002],a[200002],b[200002],s[200002],l1,r1,mx;
int stanga(int l2,int r2,int nr)
{
    if(l2>r2||l2>r1||r2<l1)
        return 0;
    int m=(l2+r2)/2;
    if(r1>=m)
    {
        mx=max(mx,a[nr]);
        return l[nr];
    }
    return stanga(l2,m,nr*2);
}
int dreapta(int l2,int r2,int nr)
{
    if(l2>r2||l2>r1||r2<l1)
        return 0;
    int m=(l2+r2)/2;
    if(l1<=m)
    {
        mx=max(mx,a[nr]);
        return r[nr];
    }
    return dreapta(m+1,r2,nr*2+1);
}
void querry(int l2,int r2,int nr)
{
    if(l1<=l2&&r2<=r1)
    {
        mx=max(mx,a[nr]);
        return;
    }
    int m=(l2+r2)/2;
    if(m>=l1&&m<=r1)
        mx=max(mx,stanga(m+1,r2,nr*2+1)+dreapta(l2,m,nr*2));
    else if(m>=r1)
        querry(l2,m,nr*2);
    else
        querry(m+1,r2,nr*2+1);
}
void baga(int l2,int r2,int nr)
{
    if(l2>r2)
        return;
    if(l2==r2)
    {
        l[nr]=r[nr]=a[nr]=b[l2];
        return;
    }
    int m=(l2+r2)/2;
    baga(l2,m,nr*2);
    baga(m+1,r2,nr*2+1);
    a[nr]=max(r[nr*2]+l[nr*2+1],max(a[nr*2],a[nr*2+1]));
    l[nr]=max(l[nr*2],s[m]-s[l2-1]+l[nr*2+1]);
    r[nr]=max(r[nr*2+1],s[r2]-s[m]+r[nr*2]);
}
int main()	
{
    int n,q,nr,i;
    in>>n>>q;
    for(i=1;i<=n;i++)
    {
        in>>b[i];
        s[i]=s[i-1]+b[i];
    }
    baga(1,n,1);
    while(q--)
    {
        in>>l1>>r1;
        mx=-(1<<29);
        querry(1,n,1);
        out<<mx<<"\n";
    }
    return 0;	
}