#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <queue>
//#include <conio.h>
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define newl printf("\n")
#define NMAX 100005
#define nst (nod<<1)
#define ndr (nst+1)
using namespace std;
int n,m,v[NMAX];
struct node
{
    long long pre,suf,totalSum,ans;
    node()
    {
        pre=suf=totalSum=ans=0LL;
    }
};
node tree[NMAX<<2];
node combine(node left,node right)
{
    node t;
    t.totalSum=left.totalSum+right.totalSum;
    t.pre=max(left.pre,left.totalSum+right.pre);
    t.suf=max(right.suf,right.totalSum+left.suf);
    t.ans=max(max(left.ans,right.ans),left.suf+right.pre);
    return t;
}
node make_node(int x)
{
    node t;
    t.totalSum=x;
    t.pre=t.suf=t.ans=x;
    return t;
}
void build(int nod,int st,int dr)
{
    if (st==dr)
    {
        tree[nod]=make_node(v[st]);
        return;
    }
    int mid=(st+dr)>>1;
    build(nst,st,mid);
    build(ndr,mid+1,dr);
    tree[nod]=combine(tree[nst],tree[ndr]);
}
node query(int nod,int st,int dr,int a,int b)
{
    if (a<=st && dr<=b) return tree[nod];
    int mid=(st+dr)>>1;
    if (b<=mid) return query(nst,st,mid,a,b);
    if (a>mid) return query(ndr,mid+1,dr,a,b);
    node left=query(nst,st,mid,a,mid);
    node right=query(ndr,mid+1,dr,mid+1,b);
    return combine(left,right);
}
int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%d",&v[i]);
    build(1,1,n);
    int a,b;
    while (m--)
    {
        scanf("%d %d",&a,&b);
        printf("%lld\n",query(1,1,n,a,b).ans);
    }
    return 0;
}