Suppose we are given an array of numbers A[0], A[2], . . . , A[n - 1]. You may assume that n is a multiple of 6. We wish to find a number x that simultaneously satisfies two properties: First, x should be in the middle two-thirds of the array (in other words, x = A[i] for some n/6 <= i < 5n/6). Second, after sorting the array, x should still be in the middle two-thirds.

2a) Prove that such an x exists. (Hint: how many values are not in the middle two-thirds of the original array? How many are not in the middle two-thirds of the sorted array?

2b) Describe a linear time algorithm for finding such an x.