#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ll;
using namespace std;

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

struct node
{
    int sum,pref,suff,ans;
};

int v[100001];
node A[400001];

node combine(node l,node r)
{
    node res;
    res.sum=l.sum+r.sum;
    res.pref=max(l.pref, l.sum+r.pref);
    res.suff=max(r.suff, r.sum+l.suff);
    res.ans=max(max(l.ans, r.ans), l.suff+r.pref);
    return res;
}
void build(int i,int st,int dr)
{
    if(st==dr)
    {
        A[i]={v[st],v[st],v[st],v[st]};
    }
    else
    {
        int m = (st+dr)/2;
        build(2*i,st,m);
        build(2*i+1,m+1,dr);
        A[i]=combine(A[2*i],A[2*i+1]);
    }
}
node query(int i,int st,int dr,int a,int b)
{
    if(a<=st && dr<=b)
    {
        return A[i];
    }
    else
    {
        int m = (st+dr)/2;
        node left,right;
        if(a <= m)
        {
             left=query(2*i,st,m,a,b);
        }
        if(b>m)
        {
            right=query(2*i+1,m+1,dr,a,b);
        }
        if(a<=m && b > m)
        {
            return combine(left,right);
        }
        return a<=m ? left : right;
    }
}

int main()
{
    int n,q;
    fin >> n >> q;
    for(int i=1;i<=n;i++)
    {
        fin >> v[i];
    }
    build(1,1,n);
    while(q--)
    {
        int t,a,b;
        fin >> a >> b;
        fout << query(1,1,n,a,b).ans << "\n";
    }


}