解説

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

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

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

想定解

C++
pypy3