题意：

给一个长为 $n$ 的序列 $a$ ，$m$ 次查询区间出现次数 $k_1$ 小的数中权值第 $k_2$ 小的。

$1 \leq n, m \leq 4 \times 10^4, 1 \leq a_i \leq n$ 。

题解：

考虑普通莫队的过程。

那么可以用分块维护已经有的数种出现次数第 $k_1$ 小的数，$\mathcal{O}(1)$ 插入删除 $\mathcal{O}(\sqrt n)$ 查询。

对于每种出现次数，同样也可以用分块维护 $kth$ ，支持 $\mathcal{O}(1)$ 插入删除 $\mathcal{O}(\sqrt n)$ 查询。

唯一的问题是，这样第二类分块总共要开 $\mathcal{O}(n)$ 个（对每种出现次数开一个），而每个分块的空间大小是 $\mathcal{O}(n)$ 的。

一种优化的策略是，比如某个数 $x$ 在整个序列中出现次数为 $cnt_x$ ，那么它可能出现在 $1, 2, \dots, cnt_x$ 这几个分块中。对于每个分块，我们只开有可能出现次数个大小的空间。这样是 $\sum_x cnt_x = n$ 的。我们需要对每个分块中可能出现的值进行离散化预处理。用 $f(x, y)$ 表示数值 $x$ 在可能出现 $y$ 次的数中的排名，把它作为其在第 $y$ 个块中的下标即可。

struct block {
#define gb(x) (((x)-1)/bs)
#define hob(x) ((x)*bs+1)
#define eob(x) min(((x)+1)*bs,n)
    int n, bs, nb;
    vector<int> cnt, tag;
    void init(int _n) {
        n = _n;
        bs = sqrt(n);
        nb = n / bs + 1;
        cnt.resize(n + 1);
        tag.resize(nb + 1);
    }
    void insert(int x) {
        if(++ cnt[x] == 1) ++ tag[gb(x)];
    }
    void erase(int x) {
        if(-- cnt[x] == 0) -- tag[gb(x)];
    }
    int qry(int k) {
        int b = 0;
        while(k > tag[b] && k) k -= tag[b ++];
        rep(i,hob(b),eob(b)) {
            if((k -= (cnt[i] > 0)) <= 0) return i;
        }
        return -1;
    }
} blk;

struct ask { int l, r, k1, k2, id; };
vector<int> belong;
inline bool mocmp(ask &a, ask &b) { return belong[a.l] ^ belong[b.l] ? belong[a.l] < belong[b.l] : belong[a.l] & 1 ? a.r < b.r : a.r > b.r; }

int n;
vector<int> a, cnt;
vector< vector<int> > f, g;
vector<vector<int>::iterator> ed;
vector<block> vb;

void prework() {
    blk.init(n);
    f.resize(n + 1), g.resize(n + 1);
    ed.resize(n + 1);
    rep(i,1,n) ++ cnt[a[i]];
    rep(i,1,n) if(cnt[i]) {
        rep(j,0,cnt[i]) g[j].push_back(i);
    }
    rep(i,1,n) if(g[i].size()) {
        sort(g[i].begin(), g[i].end());
        ed[i] = unique(g[i].begin(), g[i].end());
    }
    rep(i,1,n) if(cnt[i]) {
        f[i].resize(cnt[i] + 1);
        rep(j,1,cnt[i]) f[i][j] = lower_bound(g[j].begin(), ed[j], i) - g[j].begin() + 1;
    }
    vb.resize(n + 1);
    rep(i,1,n) if(g[i].size()) vb[i].init(ed[i] - g[i].begin());
    cnt.assign(n + 1, 0);
}

inline void add(int x) {
    if(cnt[a[x]]) {
        blk.erase(cnt[a[x]]);
        vb[cnt[a[x]]].erase(f[a[x]][cnt[a[x]]]);
    }
    ++ cnt[a[x]];
    blk.insert(cnt[a[x]]);
    vb[cnt[a[x]]].insert(f[a[x]][cnt[a[x]]]);
}

inline void del(int x) {
    blk.erase(cnt[a[x]]);
    vb[cnt[a[x]]].erase(f[a[x]][cnt[a[x]]]);
    -- cnt[a[x]];
    if(cnt[a[x]]) {
        blk.insert(cnt[a[x]]);
        vb[cnt[a[x]]].insert(f[a[x]][cnt[a[x]]]);
    }
}

inline int qry(int k1, int k2) {
    int num = blk.qry(k1);
    return g[num][vb[num].qry(k2) - 1];
}

signed main() {

    if(fopen("yl.in", "r")) {
        freopen("yl.in", "r", stdin);
        freopen("yl.out", "w", stdout);
    }
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int m;
    cin >> n;
    belong.resize(n + 1);
    a.resize(n + 1);
    cnt.resize(n + 1);
    rep(i,1,n) cin >> a[i];
    prework();
    cin >> m;
    vector< ask > as(m);
    vector<int> ans(m);
    int mbs = max(1.0, n / sqrt(m * 2.0 / 3));

    rep(i,0,n - 1) belong[i] = i / mbs + 1;

    rep(i,0,m - 1) {
        cin >> as[i].l >> as[i].r >> as[i].k1 >> as[i].k2;
        as[i].id = i;
    }

    sort(as.begin(), as.end(), mocmp);

    int l = 1, r = 0;
    for(ask &cur : as) {
        //expand first
        while(r < cur.r) add(++ r);
        while(l > cur.l) add(-- l);
        while(r > cur.r) del(r --);
        while(l < cur.l) del(l ++);
        ans[cur.id] = qry(cur.k1, cur.k2);
    }
    rep(i,0,m - 1) cout << ans[i] << endl;
    return 0;
}