You are given an integer r [1..n] and a sequence o = $81, 82, ..., Sn of n distinct elements in which elements are presented one at a time. When element s; is presented, you can no longer access any of $1,..., Si-1 unless your algorithm has stored them. You are asked to output the rth smallest element in o. Design an algorithm that can accomplish this using O(r) space and O(n) expected time. (25 points)