#include <stdio.h>

#define INF 1LL * 1000000000 * 1000000000
#define nMax 100001
#define l 2*node
#define r 2*node+1
using namespace std;
int n, m;
int v[nMax];
long long Sol, Suma;
long long St[4*nMax], Dr[4*nMax], Mid[4*nMax], Sum[4*nMax];
long long max(long long a, long long b)
{
    if(a<b)
        return b;
    return a;
}
void read()
{
    scanf("%d%d", &n, &m);

    for(int i=1;i<=n;i++)
        scanf("%d", &v[i]);
}
void verif(int node, int st, int dr)
{
    int mid=st+(dr-st)/2;

    St[node]=St[l];
    if(Sum[l]+St[r]>St[node])
        St[node]=Sum[l]+St[r];

    Dr[node]=Dr[r];
    if(Sum[r]+Dr[l]>Dr[node])
        Dr[node]=Sum[r]+Dr[l];

    Mid[node]=max(Dr[l]+St[r], max(Mid[l], Mid[r]));
    Sum[node]=Sum[l]+Sum[r];
}
void build(int node, int st, int dr)
{
    if(st==dr)
    {
        St[node]=Dr[node]=Mid[node]=Sum[node]=v[st];
        return;
    }

    int mid=st+(dr-st)/2;
    build(l, st, mid);
    build(r, mid+1, dr);

    verif(node, st, dr);
}
void query(int node, int st, int dr, int pozst, int pozdr)
{
    if(st>=pozst && dr<=pozdr)
    {
        Sol=max(Sol, Mid[node]);

        if(Suma<0)
            Suma=0;
        Sol=max(Sol, Suma+St[node]);
        Suma=max(Suma+Sum[node], Dr[node]);

        return;
    }

    int mid=st+(dr-st)/2;
    if(pozst<=mid)
        query(l, st, mid, pozst, pozdr);
    if(pozdr>mid)
        query(r, mid+1, dr, pozst, pozdr);
}
void solve()
{
    int a, b;
    build(1, 1, n);

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d", &a, &b);
        Sol=-INF, Suma=0;
        query(1, 1, n, a, b);
        printf("%lld\n", Sol);
    }
}
int main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);

    read();
    solve();

    return 0;
}