#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;
}