#include <bits/stdc++.h>
#define Nmax 100002
#define INF 1LL * 20000000002
#define LL long long
FILE *fin  = freopen("sequencequery.in", "r", stdin);
FILE *fout = freopen("sequencequery.out", "w", stdout);

using namespace std;
int n, m, sum[Nmax];
LL sol = -INF, F = -INF;
struct tree
{
    LL x;
    LL start;
    LL finish;
} T[4 * Nmax];
LL Max(LL x, LL y)
{
    if(x > y)
        return x;
    return y;
}
void update(int node, int L, int R, int pos, int val)
{
    int lson = 2 * node, rson = 2 * node + 1;
    if(L == R)
    {
        T[node].x = T[node].start =
                        T[node].finish = 1LL * val;
    }

    else
    {
        int mid = (L + R) >> 1;

        if(pos <= mid)
            update(lson, L, mid, pos, val);
        else
            update(rson, mid + 1, R, pos, val);

        /// update the maximal sum subsequence
        T[node].x = 1LL * Max(T[lson].x, T[rson].x);
        T[node].x = 1LL * Max(T[node].x, T[lson].finish + T[rson].start);
        T[node].x = 1LL * Max(T[node].x, T[lson].finish);
        T[node].x = 1LL * Max(T[node].x, T[rson].start);

        /// update finish subsequence
        T[node].finish = Max(T[rson].finish,
                             sum[R] - sum[mid] + T[lson].finish);
        /// update start  subsequence
        T[node].start = Max(T[lson].start,
                            sum[mid] - sum[L - 1] + T[rson].start);
    }

}
void query(int node, int L, int R, int l, int r)
{
    int lson = 2 * node, rson = 2 * node + 1;
    if(r < L || l > R)
        return;

    if(l <= L && r >= R)
    {
        sol = Max(sol, Max(T[node].x, F + T[node].start));
        F = Max(T[node].finish, sum[R] - sum[L - 1] + F);
        return;
    }

    int mid = (L + R) >> 1;
    query(lson, L, mid, l, r);
    query(rson, mid + 1, R, l, r);
}
void build()
{
    int i, x;
    scanf("%d %d", &n, &m);
    for(i = 1; i <= n; ++ i)
    {
        scanf("%d", &x);
        sum[i] = sum[i - 1] + x;
        update(1, 1, n, i, x);
    }
}
void queries()
{
    int l, r;
    while(m --)
    {
        scanf("%d %d", &l, &r);
        query(1, 1, n, l, r);
        printf("%lld\n", sol);
        sol = -INF;
        F = -INF;
    }
}
initial()
{
    for(int i = 1; i < 4 * Nmax; ++ i)
        T[i].x = T[i].start = T[i].finish = -INF;
}
int main()
{
    initial();
    build();
    queries();
    return 0;
}