1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <map>
#include <cstdio>
#include <algorithm>
using namespace std;
int getint() {
    int r = 0, k = 1; char c = getchar();
    for (; c < '0' || c > '9'; c = getchar()) if (c == '-') k = -1;
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r * k;
}
map<int, int> M;
const int N = 500005;
const int mxlog = 30;
int n, m, ans, K, H[N], siz[N * mxlog], lc[N * mxlog], rc[N * mxlog], tot, cnt, a[N], root[N], l, r;
void sgtQuery(int x, int y, int l, int r) {
    if (l == r) {
        ans = l;
        return;
    }
    int mid = (l + r) >> 1;
    if (siz[lc[x]] - siz[lc[y]] > K) sgtQuery(lc[x], lc[y], l, mid);
    if (siz[rc[x]] - siz[rc[y]] > K) sgtQuery(rc[x], rc[y], mid+1, r);
}
void sgtChange(int &x, int y, int l, int r, int pos) {
    x = ++tot;
    lc[x] = lc[y];
    rc[x] = rc[y];
    siz[x] = siz[y] + 1;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) sgtChange(lc[x], lc[y], l, mid, pos);
    else sgtChange(rc[x], rc[y], mid+1, r, pos);
}
int main() {
    n = getint(); m = getint();
    for (int i = 1; i <= n; ++i) {
        a[i] = getint();
        M[a[i]] = 0;
    }
    for (map<int, int>::iterator it = M.begin(); it != M.end(); ++it) {
        it->second = ++cnt;
        H[cnt] = it->first;
    }
    for (int i = 1; i <= n; ++i)
        sgtChange(root[i], root[i-1], 1, cnt, M[a[i]]);
    for (int i = 1; i <= m; ++i) {
        l = getint(); r = getint(); ans = 0; K = (r - l + 1) >> 1;
        sgtQuery(root[r], root[l-1], 1, cnt);
        printf("%d\n", H[ans]);
    }
}