Doesn't that imply a linear "n largest" algorithm? I guess that might already exist, but I wasn't aware of that!
As the sibling comment points out, that's not news. But it's very good for you to pick up that implication from first principles alone. It's part of figuring out how to solve this.
But this reduction from 'select n largest' to my problem is still instructive: it tells us that in some sense any (deterministic) solution to my pet problem has to be at least as complicated as (deterministic) median finding.