There is a well known worst case $O(n)$ selection algorithm to find the $k$'th largest element in an array of integers. It uses a median-of-medians approach to find a good enough pivot, partitions the input array in place and then recursively continues in it's search for the $k$'th largest element.
What if we weren't allowed to touch the input array, how much extra space would be needed in order to find the $k$'th largest element in $O(n)$ time? Could we find the $k$'th largest element in $O(1)$ extra space and still keep the runtime $O(n)$? For example, finding the maximum or minimum element takes $O(n)$ time and $O(1)$ space.
Intuitively, I cannot imagine that we could do better than $O(n)$ space but is there a proof of this?
Can someone point to a reference or come up with an argument why the $\lfloor n/2 \rfloor$'th element would require $O(n)$ space to be found in $O(n)$ time?