Алгоритм O (n) для нахождения медианы набора чисел

Проблема: входные данные представляют собой (не обязательно отсортированную) последовательность S = k1, k2, ..., kn из n произвольных чисел. Рассмотрим набор C из n² чисел вида min {ki, kj} для 1 <= i, j <= n. Представьте алгоритм O (n) времени и O (n) , чтобы найти медиану C.

До сих пор, исследуя C для различных наборов S, я обнаружил, что количество экземпляров наименьшего числа в S в C равно (2n-1), следующее наименьшее число: (2n-3) и так далее, пока у вас не будет только один экземпляр наибольшего числа.

Есть ли способ использовать эту информацию, чтобы найти медиану C?