You have recently been hired to work for a large social media company. The company has staff shortages due to a recent firing spree, and you have been tasked with designing the recommendation algorithm used on the front page! After thinking for several days, you have figured out a way to measure a user's popularity, and now need to design an efficient algorithm to calculate it. For a given user with n posts, you have access to an integer array V=[v1,v2,,vn], where vi is the number of views the user's ith post has in thousands. Since these view counts are used to order posts on a user's profile page, they are already sorted, in descending order. The popularity of a user is the largest value of p such that the user has at least p posts that each have at least p thousand views. For example, suppose a user has n=6 posts, and a view count array V=[7,6,5,4,4,1]. Then they have at least 4 posts each with at least 4,000 views (indeed, they have five such posts), so p=4 satisfies the criterion. You can confirm that the criterion is also satisfied for p=3, but it is not satisfied for p=5 since there are only three qualifying posts. The user's popularity index is in fact 4 , because p=4 is the largest value for which the criterion holds. 1.1 [7 marks] Before you are given full access to the codebase, you need to try and implement your new popularity measure on top of the existing code. Given the integer n and the integer array V for a user as well as an integer value pn, you must determine whether that user's popularity is at least p. This snippet of code runs every single time the page gets loaded, so it needs to be very efficient. Design an algorithm that runs in O(1) time and checks whether a user's popularity is at least p. 1.2 [13 marks] The code you modified was written by a now-fired intern, and would simply try every value of p until it found one that worked, for every user. Now that the company has grown to serve millions of users, your boss has demanded that you develop a faster algorithm. Given the integer n and the integer array V for a user, you must efficiently compute the user's popularity index p. Design an algorithm that runs in O(logn) time and computes p for a given user