wavelet matrix で解けます。

wavelet matrix は、整数列 \(a = (a_0, a_1, \dots, a_{n-1})\) に関して

• 区間 \([l, r)\) のうちで \(x\) 以下のものの個数は？
• 区間 \([l, r)\) のうちで \(x\) 未満のものの個数は？
• 区間 \([l, r)\) のうちで \(x\) 以上のものの個数は？
• 区間 \([l, r)\) のうちで小さい方から \(k\) 番目の値は？

というクエリを \(O(\log(\max_i a_i))\) 時間で処理できます。

値の更新クエリは難しい（できなくはないが）ので、クエリを先読みし、追加クエリを全部処理したときの \(A\) を用意しておきます。 その上で、\([l, r) \gets [0, 0)\) で初期化しておきます。

便宜上、現在の \([l, r)\) において \(x\) 以下のものの個数を \(c_{\le x}\) と書きます。未満・以上についても同様に \(c_{\lt x}\), \(c_{\ge x}\) と書きます。

各クエリに対して以下のことをします。 クエリ 2, 3 の \(k\) は 0-indexed に変換しておきます(i.e. \(k\gets k-1\)) 。

• クエリ 1
  • \(r \gets r+1\) で更新。
• クエリ 2
  • \(c_{\le x} \le k\) であれば -1 を出力。
  • そうでなければ、小さい方から \((c_{\le x}-k-1)\) 番目の値を出力。
• クエリ 3
  • \(c_{\ge x} \le k\) であれば -1 を出力。
  • そうでなければ、小さい方から \((c_{\lt x} + k)\) 番目の値を出力。

座標圧縮したりしなかったりすることで、\(O(Q\log(x))\) 時間や \(O(Q\log(Q))\) 時間で解けます。