Как найти среднее значение верхней половины N чисел?

Для N произвольных целых чисел, как найти среднее значение верхней половины этих чисел? Есть ли решение O (n)? Если нет, можно ли доказать, что это невозможно?