#include <bits/stdc++.h>

using namespace std;

#define ws " "
#define newl "\n"
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define _sz(x) (int) x.size()
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define yes cout << "yes\n"
#define no cout << "no\n"

const int INF = (int) 1e9;
const ll ll_INF = (ll) 1e18;
const ll MOD = 1e9 + 7;

struct Node {
    int l = 0, r = 0;
    ll sum = 0;
    Node() {}
    Node(int _l, int _r, ll _s): l(_l), r(_r), sum(_s) {}
};

int n, q;
vector<ll> a;
vector<ll> vals;
vector<Node> seg;
vector<int> roots;
int m;

// create new node and return its index
inline int new_node() {
    seg.emplace_back();
    return (int)seg.size() - 1;
}

// persistently update position 'pos' by adding 'val'
// prev_root is index of previous version root
int update(int prev_root, int tl, int tr, int pos, ll val) {
    int cur = new_node();
    seg[cur] = seg[prev_root];         // copy previous node
    seg[cur].sum += val;
    if (tl == tr) return cur;
    int mid = (tl + tr) >> 1;
    if (pos <= mid) {
        seg[cur].l = update(seg[prev_root].l, tl, mid, pos, val);
    } else {
        seg[cur].r = update(seg[prev_root].r, mid + 1, tr, pos, val);
    }
    return cur;
}

// query sum on value-index range [lq, rq] in specified root
ll query_sum(int root, int tl, int tr, int lq, int rq) {
    if (root == 0 || lq > rq) return 0;
    if (lq <= tl && tr <= rq) return seg[root].sum;
    int mid = (tl + tr) >> 1;
    ll res = 0;
    if (lq <= mid) res += query_sum(seg[root].l, tl, mid, lq, min(rq, mid));
    if (rq > mid)  res += query_sum(seg[root].r, mid+1, tr, max(lq, mid+1), rq);
    return res;
}



void solve() {
    if (!(cin >> n >> q)) return;
    a.assign(n+1, 0);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // coordinate compress values
    vals.reserve(n);
    for (int i = 1; i <= n; ++i) vals.push_back(a[i]);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    m = (int)vals.size();

    // reserve space for persistent segment tree nodes
    // estimate: about n * (log2(m) + 2) nodes
    seg.reserve((size_t)( (ll)(n + 5) * 20 ));
    seg.emplace_back(); // index 0 is the null node

    roots.assign(n+1, 0);
    roots[0] = 0;

    // build persistent versions: root[i] contains prefix 1..i
    for (int i = 1; i <= n; ++i) {
        int pos = int(lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin()) + 1; // 1-based
        roots[i] = update(roots[i-1], 1, m, pos, a[i]);
    }

    // answer queries
    while (q--) {
        int l, r; cin >> l >> r;
        ll curr = 0;               // we can form [1..curr], initial curr = 0
        ll sum_le_prev = 0;       // sum of elements <= prev threshold (prev threshold = 0 initially)

        while (true) {
            ll T = curr + 1; // threshold
            int pos = int( upper_bound(vals.begin(), vals.end(), T) - vals.begin() ); // number of distinct values <= T
            if (pos == 0) {
                // no elements with value <= T, inc == 0
                break;
            }
            ll sum_le_T = query_sum(roots[r], 1, m, 1, pos) - query_sum(roots[l-1], 1, m, 1, pos);
            ll inc = sum_le_T - sum_le_prev; // newly available coins in (prev_threshold, T]
            if (inc == 0) break;
            curr += inc;
            sum_le_prev = sum_le_T;
            // loop will run O(log total_sum) times because curr at least doubles on successful iteration
        }
        cout << (curr + 1) << '\n';
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(__null); cout.tie(__null);

    int t = 1;
    // cin >> t;

    while(t--) solve();

    return 0;
}