#include <cstdio>
#define inf 1000000000

using namespace std;
typedef long long llong;

struct JuglansRegia
{
    llong best, sum, st, dr;
} arb[270000];
int v[100004];
int n, nq;
int ist, idr;
llong sum, rez;

llong mmax(llong a, llong b)
{
    return a > b ? a : b;
}

void build(int st, int dr, int poz)
{
    if(st == dr) {
        arb[poz].best = arb[poz].sum = arb[poz].st = arb[poz].dr = v[st];
    }
    else {
        int mid = (st + dr) / 2;
        build(st, mid, poz * 2);
        build(mid + 1, dr, poz * 2 + 1);
        arb[poz].best =
            mmax(
                 mmax(
                      arb[poz * 2].best,
                      arb[poz * 2 + 1].best),
                 arb[poz * 2].dr + arb[poz * 2 + 1].st);
        arb[poz].st =
            mmax(
                 arb[poz * 2].st,
                 arb[poz * 2].sum + arb[poz * 2 + 1].st);
        arb[poz].dr =
            mmax(
                 arb[poz * 2 + 1].dr,
                 arb[poz * 2 + 1].sum + arb[poz * 2].dr);
        arb[poz].sum = arb[poz * 2].sum + arb[poz * 2 + 1].sum;
    }
}

void query(int st, int dr, int poz)
{
    if(ist <= st && dr <= idr)
    {
        if(sum < 0)
            sum = 0;
        rez =
            mmax(
                rez,
                mmax(
                    arb[poz].best,
                    sum + arb[poz].st));
        sum = mmax(sum + arb[poz].sum, arb[poz].dr);
    }
    else
    {
        int mid = (st + dr) / 2;
        if(ist <= mid)
            query(st, mid, poz * 2);
        if(mid < idr)
            query(mid + 1, dr, poz * 2 + 1);
    }
}

int main()
{
    int i;
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    scanf("%d%d", &n ,&nq);
    for(i = 1; i <= n; i++) scanf("%d", &v[i]);
    build(1, n, 1);
    for(i = 0; i < nq; i++)
    {
        scanf("%d%d", &ist, &idr);
        rez = -inf;
        sum = 0;
        query(1, n, 1);
        printf("%lld\n", rez);
    }
    return 0;
}