より一般に、与えられた配列に対して「区間 \([l, r)\) で小さい方から \(k\) 番目の値を求めてね」という形式の問題も解くことができます。

以下では、wavelet matrix というデータ構造を用いる方法と、並列二分探索というアルゴリズムを用いる方法を紹介しています。

https://rsk0315.hatenablog.com/entry/2022/01/09/152028

難易度は元の問題よりも多少高いと思われるので、無理に考える必要はありませんが、興味のある人の助けになれば幸いです。

（追記）他にも、平方分割や range tree を使う方法などもあります。蟻本 pp. 168–172 に載っています。