#include <bits/stdc++.h>
#define inf 1e12
using namespace std;

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

int n,m,i,x,y;

int v[100001];

long long ans,sum;

struct nod{long long Max,st,dr,tot;}a[400010];

void build(int nod,int l,int r)
{
    if(l==r)
    {
        a[nod].st=a[nod].dr=a[nod].Max=a[nod].tot=v[l];
        return ;
    }
    int m=(l+r)/2;
    build(nod*2,l,m);
    build(nod*2+1,m+1,r);
    a[nod].tot=a[nod*2].tot+a[nod*2+1].tot;
    a[nod].st=max(a[nod*2].st,a[nod*2].tot+a[nod*2+1].st);
    a[nod].dr=max(a[nod*2+1].dr,a[nod*2+1].tot+a[nod*2].dr);
    a[nod].Max=max(a[nod*2].Max,max(a[nod*2+1].Max,a[nod*2].dr+a[nod*2+1].st));
}

void query(int nod,int l,int r,int st,int dr)
{
    if(st<=l&&r<=dr)
    {
        ans=max(ans,max(a[nod].Max,a[nod].st+sum));
        sum=max(a[nod].dr,a[nod].tot+sum);
        return ;
    }
    int m=(l+r)/2;
    if(st<=m)query(nod*2,l,m,st,dr);
    if(m<dr)query(nod*2+1,m+1,r,st,dr);
}

int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
        fin>>v[i];
    build(1,1,n);
    for(i=1;i<=m;i++)
    {
        fin>>x>>y;
        ans=sum=-inf;
        query(1,1,n,x,y);
        fout<<ans<<'\n';
    }
    return 0;
}