二分探索し、「最小値は \(x\) 以上か？」という判定問題を解きます。

最小値が \(x\) 以上であることは、 \(x\) 未満の値が存在しない、すなわち全て取り出されていることと同値です。つまり、元の値および取り出された値をソートし、二分探索により \(x\) 未満の値の個数を求め、等しいかどうか確認すれば良いです。

計算量は \(O(\sum K\log N\log\max A)\) であり十分高速です。

コード(C++)