C - Linear Search?

解説

線形探索を行う解法だと、最悪 $O(NQ)$ 回の探索が必要になってしまい、TLEしてしまいます。
そこで、キーを「$A$ の要素 $x$」、値を「$A_k = x$ を満たす $k$ の順序付き集合」となる連想配列 $D$ を考え、以下のようにクエリを処理することで、十分高速に処理することができます。

1 i x： $D[A_i]$ から $i$ を削除し、$D[x]$ に $i$ を追加する。そして、 $A_i$ を $x$ に更新する。
2 x： $D[x]$ の最小値を取得する。
3 x： $D[x]$ の最大値を取得する。

C++ だと標準ライブラリの map や set を用いて処理することができます。 Python の場合、 MojaCoder 環境では自作するか有志の方が作ってくれたSortedSet を使うなどの方法で処理をする必要があります。

想定解