「出現回数が \(c\) 回の要素を追加する操作」をまとめて「ステップ \(c\) 」と呼ぶことにします。

ステップ \(c\) は「\(A\) における出現回数が \(c\) 以下の値を昇順に追加する」ことになるはずです。このときに追加される値を順に並べた配列を \(B_c\) とします。

この \(B_c\) は高々 \(O(\sqrt N)\) 回しか変化しません。

よって、すべての \(B_c\) の列挙が（ \(B_c\) がおなじ \(c\) を適切にまとめれば）空間・時間計算量ともに \(O(M\sqrt N)\) です。メモリに余裕があればこれを列挙しても構いませんが、今回の制約下ではおそらく MLE となるでしょう。

しかし、\(c\) の昇順にクエリを処理しながら \(B_c\) を適宜再構築すれば、空間計算量に余裕が生まれるため、高速な言語であれば AC 可能です。時間計算量は全体で \(O(M \sqrt N + Q \log Q)\) 空間計算量は \(O(N + M + Q)\) となります。

実装例 codon

from bisect import bisect_right
from heapq import heapify, heappop

n, m = [int(v) for v in input().split()]
a = [int(v) for v in input().split()]

c = [0] * (m + 1)
for x in a:
    c[x] += 1

mc = max(c)
ch = [0] * (mc + 1)
for x in range(1, m + 1):
    ch[c[x]] = 1

q = int(input())
que = [(int(input())-1, i) for i in range(q)]
heapify(que)
ans = [0] * q

while que and que[0][0] < n:
    x, i = heappop(que)
    ans[i] = a[x]

l = n
b = []
for nc in range(mc + 1):
    if ch[nc]:
        b = [x for x in range(1, m + 1) if c[x] <= nc]
    l += len(b)  
    while que and que[0][0] < l:
        x, i = heappop(que)
        ans[i] = b[x-l+len(b)]
else:
    while que:
        x, i = heappop(que)
        ans[i] = (x-l) % m + 1

print("\n".join(map(str, ans)))

p.s. 空間計算量に余裕があれば、この解法はオンラインクエリに対応できる解法です。しかし、クエリ先読みをするのであれば、想定解の実装にほとんど合流する（対数時間の要素の追加ではなく、単に愚直な再構築でよいというのみ）ということになるでしょう。