(15 points) For n distinct elements a1,,an with positive weights w1,,wn s.t. i=1nwi=1 design a linear-time algorithm returning the element ak, which satisfies the following: aiakwi1/2. Assume that such an ak always exists. You should also justify the time complexity