Recall the Partition subroutine that we used in both QuickSort and RSelect. Suppose that the following array has just been partitioned around some pivot element: 3, 1, 2, 4, 5, 8, 7, 6, 9.
Which of these elements could have been the pivot element? (Hint: There could be more than one possibility!)