クエリ平方分割でも解けます．

まず，クエリで出てくる値を先読みしてソートしておきます．このとき，同じ値であれば，クエリ \(3\), \(1\), \(2\) の順に並ぶようにしておきます．（ \(3\) からは右に，\(2\) からは左に向かって探索し，同じ値の出現を探索に含めるためです．具体的には，ソートするときのキー値をすべて \(3\) 倍しておき，クエリ \(3\) であれば \(-1\) ，クエリ \(2\) であれば \(+1\) するなどすればよいです．）

ソート済みの各位置から見て直近にあるクエリ \(1\) 済みの位置（左右）を覚えておけば，クエリ \(3\), \(2\) に対しては高々 \(5\) 回左右に移動することでクエリに正しく回答できます．

毎回この情報を更新して管理するのは大変なので，クエリ \(1\) を \(\sqrt{Q}\) 回程度処理するごとに全体を最新状態に更新することにします．全体の更新は配列全体を \(1\) 往復する程度で可能であり，更新自体が全体を通して高々 \(Q / \sqrt{Q} = \sqrt{Q}\) 回程度しか起こらないため，この操作にかかる計算量は全体を通して \(\mathrm{O}(Q\sqrt{Q})\) となります．

未反映のクエリは常に高々 \(\sqrt{Q}\) 個程度なので，これらはクエリ \(2\), \(3\) を処理するときに適宜処理することにします．具体的には，まず未反映のクエリを無視して解の候補（高々 \(5\) 個）を求め，それらと未反映のクエリによって追加される値を適宜比較することで，解の候補を更新します．クエリ \(1\) 回あたりの比較の回数が \(\mathrm{O}(\sqrt{Q})\) 回なので，こちらの操作にかかる計算量も全体を通して \(\mathrm{O}(Q \sqrt{Q})\) となります．

よって全体 \(\mathrm{O}(Q \sqrt{Q})\) 時間でこの問題が解け，隠れている定数倍を考慮して閾値を適切に設定することで実行時間制限に余裕を持って間に合わせることが可能です．

実装例 (C, 200 ms)