#include <iostream>
#include <fstream>

using namespace std;

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

const int64_t INF = 100005;
int v[100005];

struct branch
{
    int64_t s = -INF, l = -INF, r = -INF, m = -INF;
} tree[400400];

void build(int node, int left, int right) {
    if(left == right) {
        tree[node].s = v[left];
        tree[node].m = v[left];
        tree[node].l = v[left];
        tree[node].r = v[left];
        return;
    }

    int mid = (left+right) >> 1;
    int ls = node << 1, rs = ls | 1;

    build(ls, left, mid);
    build(rs, mid+1, right);

    tree[node].s = tree[ls].s + tree[rs].s;
    tree[node].l = max(tree[ls].l, tree[ls].s + tree[rs].l);
    tree[node].r = max(tree[rs].r, tree[rs].s + tree[ls].r);
    tree[node].m = max(tree[ls].m, max(tree[rs].m, tree[ls].r + tree[rs].l));
}

void query(int ql, int qr, int node, int left, int right, int64_t &rez, int64_t &best)
{
    if(left > qr || right < ql)
        return;

    if(ql <= left && right <= qr) {
        rez = max(rez, max(tree[node].m, best + tree[node].l));
        best = max(best + tree[node].s, tree[node].r);
        return;
    }

    int mid = (left+right) >> 1;
    int ls = node<<1, rs = ls | 1;

    query(ql, qr, ls, left, mid, rez, best);
    query(ql, qr, rs, mid+1, right, rez, best);
}

int main()
{
    int n, m;
    in >> n >> m;

    for(int i = 1; i <= n; i++)
        in >> v[i];

    build(1, 1, n);

    while(m) {
        int x,y;
        int64_t rez = -INF, best = -INF;
        in >> x >> y;
        query(x, y, 1, 1, n, rez, best);
        out << rez << '\n';
        m--;
    }

    return 0;
}