#include <cstdio>
#include <algorithm>

using namespace std;

const int N_MAX = 100000;
const int INF = 100000;

struct interval
{
    long long sum_start;
    long long sum_end;
    long long sum_max;
    long long sum_all;
};

interval arbint[800050];

long long v[N_MAX + 1];
long long s, answer2;
int x, y;

void build(int node, int left, int right)
{
    int mid;
    if(left == right)
        arbint[node].sum_max = arbint[node].sum_start = arbint[node].sum_end = arbint[node].sum_all = v[left];
    else
    {
        mid = (left + right) / 2;
        build(2 * node, left, mid);
        build(2 * node + 1,mid + 1, right);
        arbint[node].sum_max = max(arbint[2 * node].sum_max, max(arbint[2 * node + 1].sum_max, arbint[2 * node].sum_end + arbint[2 * node + 1].sum_start));
        arbint[node].sum_start = max(arbint[2 * node].sum_start, arbint[2 * node].sum_all + arbint[2 * node + 1].sum_start);
        arbint[node].sum_end = max(arbint[2 * node + 1].sum_end, arbint[2 * node + 1].sum_all + arbint[2 * node].sum_end);
        arbint[node].sum_all = arbint[2 * node].sum_all + arbint[2 * node + 1].sum_all;
    }
}

void query(int node,int left,int right)
{
    int mid;
    if(x <= left && right <= y)
    {
        answer2 = max(answer2, max(s + arbint[node].sum_start, arbint[node].sum_max));
        s = max(s + arbint[node].sum_all, arbint[node].sum_end);
    }
    else
    {
        mid=(left + right) / 2;
        if(x <= mid)
            query(2 * node, left, mid);
        if(y >= mid + 1)
            query(2 * node + 1, mid + 1, right);
    }
}

int main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);
    int n, m, i;
    scanf("%d%d", &n, &m);
    for(i = 1; i <= n; i++)
        scanf("%lld", &v[i]);
    build(1, 1, n);
    for(i = 1; i <= m; i++)
    {
        scanf("%d%d", &x, &y);
        s = 0;
        answer2 = -INF;
        query(1, 1, n);
        printf("%lld\n", answer2);

    }
    return 0;
}