#include <bits/stdc++.h>
#define Nmax 100002
#define ll long long
using namespace std;

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

int N, Q, Max;
int v[Nmax], le[Nmax], ri[Nmax], tree[4 * Nmax];
ll sum[Nmax], sum1[Nmax], sum2[Nmax], ssm;

void update(int node, int le, int ri, int pos, int val) {
    if (le == ri) tree[node] = val;
    else {
        int mid = (le + ri) / 2;
        if (pos <= mid) update(2 * node, le, mid, pos, val);
        else update(2 * node + 1, mid + 1, ri, pos, val);
        tree[node] = max(tree[2 * node], tree[2 * node] + 1) ;
    }
}
void query(int node, int le, int ri, int a, int b) {
    if (le >= a && ri <= b) Max = max(Max, tree[node]);
    else {
        int mid = (le + ri) / 2;
        if (a <= mid) query(2 * node, le, mid, a, b);
        if (mid < b) query(2 * node + 1, mid + 1, ri, a, b);
    }
}

ll calc(int x, int y) {
    ll ans = sum[y] - sum[x - 1];
    int i = le[x], j = ri[y];
    if (sum1[x] >= 0) i = x - 1;
    if (sum2[y] >= 0) j = y + 1;

    if (i >= j) {
         Max = -Nmax;
         query(1, 1, N, x, y);
         return Max;
    }
    return ans - (sum[i] - sum[x - 1]) - (sum[y] - sum[j - 1]);
}
int main()
{
    fin >> N >> Q;
    for (int i = 1; i <= 4 * N; ++i)
        tree[i] = -Nmax;
    for (int i = 1; i <= N; ++i)
        fin >> v[i], sum[i] = sum[i - 1] + v[i], update(1, 1, N, i, v[i]);

    ri[1] = 1, sum2[1] = ssm = v[1];
    for (int i = 2; i <= N; ++i) {
        ri[i] = ri[i - 1];
        if (v[i] < ssm + v[i]) ssm = v[i], ri[i] = i;
        else ssm += v[i];
        sum2[i] = ssm;
    }

    le[N] = N, sum1[N] = ssm = v[N];
    for (int i = N - 1; i >= 1; --i) {
        le[i] = le[i + 1];
        if (v[i] < ssm + v[i]) ssm = v[i], le[i] = i;
        else ssm += v[i];
        sum1[i] = ssm;
    }


    while (Q--) {
        int x, y;
        fin >> x >> y;
        fout << calc(x, y) << '\n';
    }

    return 0;
}