1 /************************************************************** 2     Problem: 3524 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:6340 ms 7     Memory:119984 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <algorithm>12  13 using namespace std;14  15 struct segment{16     int lson, rson, cnt;17 }seg[10000010];18  19 int size, m, n, L, R, M, root[510000];20  21 void insert(int p, int &q, int l, int r, int X){22     seg[++size] = seg[p], q = size;23     ++seg[size].cnt;24     if (l == r) return;25     int mid = (l + r) >> 1;26     if (mid >= X)27         insert(seg[p].lson, seg[q].lson, l, mid, X);28     else insert(seg[p].rson, seg[q].rson, mid + 1, r, X);29 }30  31 int query(int Lx, int Rx, int k, int l, int r){32     if (l == r) return l;33     int mid = (l + r) >> 1;34     if (seg[seg[Rx].lson].cnt - seg[seg[Lx].lson].cnt > k)35         return query(seg[Lx].lson, seg[Rx].lson, k, l, mid);36     if (seg[seg[Rx].rson].cnt - seg[seg[Lx].rson].cnt > k)37         return query(seg[Lx].rson, seg[Rx].rson, k, mid + 1, r);38     return 0;39 }40  41 int main(){42     scanf("%d%d", &n, &m);43     size = 0, root[0] = 0;44     for (int i = 1; i <= n; ++i){45         scanf("%d", &M);46         insert(root[i - 1], root[i], 1, n, M);47     }48  49     for (int i = 1; i <= m; ++i){    50         scanf("%d%d", &L, &R);51         if (L > R) swap(L, R);52         M = (R - L + 1) >> 1;53         printf("%d\n", query(root[L - 1], root[R], M, 1, n));54     }55     return 0;56 }