#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 1000 * 1000 * 1000 + 5;

struct NodeSum {
    long long val;
    NodeSum *l, *r;

    NodeSum(long long _val): val(_val), l(0), r(0) {}

    NodeSum(NodeSum *_l, NodeSum *_r):
        val((_l? _l->val : 0) + (_r? _r->val : 0)), l(_l), r(_r) {}
};

struct NodeMin {
    int val;
    NodeMin *l, *r;

    NodeMin(int _val): val(_val), l(0), r(0) {}

    NodeMin(NodeMin *_l, NodeMin *_r):
        val(min((_l? _l->val : INF), (_r? _r->val : INF))), l(_l), r(_r) {}
};

const int MAXN = 150 * 1000 + 5;
int a[MAXN];
pair<int, int> p[MAXN];
NodeSum *stsum[MAXN];
NodeMin *stmin[MAXN];

NodeSum *buildstsum() {
    NodeSum *res = new NodeSum(0);
    for(int i = 0; i < 20; i++)
        res = new NodeSum(res, res);
    return res;
}

NodeSum *update(NodeSum *v, int tl, int tr, int pos, int val) {
    if(tl == tr - 1)
        return new NodeSum(val);
    int tm = (tl + tr) / 2;
    if(pos < tm)
        return new NodeSum(update(v->l, tl, tm, pos, val), v->r);
    else
        return new NodeSum(v->l, update(v->r, tm, tr, pos, val));
}

long long get(NodeSum *v, int tl, int tr, int l, int r) {
    if(tl == l && tr == r)
        return v->val;
    int tm = (tl + tr) / 2;
    long long res = 0;
    if(l < tm)
        res += get(v->l, tl, tm, l, min(r, tm));
    if(r > tm)
        res += get(v->r, tm, tr, max(l, tm), r);
    return res;
}

NodeMin *buildstmin() {
    NodeMin *res = new NodeMin(INF);
    for(int i = 0; i < 20; i++)
        res = new NodeMin(res, res);
    return res;
}

NodeMin *update(NodeMin *v, int tl, int tr, int pos, int val) {
    if(tl == tr - 1)
        return new NodeMin(val);
    int tm = (tl + tr) / 2;
    if(pos < tm)
        return new NodeMin(update(v->l, tl, tm, pos, val), v->r);
    else
        return new NodeMin(v->l, update(v->r, tm, tr, pos, val));
}

int get(NodeMin *v, int tl, int tr, int l, int r) {
    if(tl == l && tr == r)
        return v->val;
    int tm = (tl + tr) / 2, res = INF;
    if(l < tm)
        res = min(res, get(v->l, tl, tm, l, min(r, tm)));
    if(r > tm)
        res = min(res, get(v->r, tm, tr, max(l, tm), r));
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        p[i] = make_pair(a[i], i);
    }
    sort(p, p + n);
    stsum[0] = buildstsum();
    for(int i = 0; i < n; i++)
        stsum[i + 1] = update(stsum[i], 0, n, p[i].second, p[i].first);
    stmin[n] = buildstmin();
    for(int i = n - 1; i >= 0; i--)
        stmin[i] = update(stmin[i + 1], 0, n, p[i].second, p[i].first);
    for(int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        long long s = 1;
        while(true) {
            int x;
            if(s > INF)
                x = INF;
            else {
                x = lower_bound(p, p + n, make_pair((int)s, 0)) - p;
                x = get(stmin[x], 0, n, l, r);
            }
            int pp = lower_bound(p, p + n, make_pair(x, 0)) - p;
            s = get(stsum[pp], 0, n, l, r) + 1;
            if(x > s || x == INF) {
                cout << s << '\n';
                break;
            }
            s += x;
        }
    }
    return 0;
}