2. Consider the following algorithm to answer the following question. Let n 2 0 be the number of people in line. This algorithm takes as input a list ai,.. . , an of heights, in centimeters, of the people in line, starting with the height a1 of the first person in the line. We assume for simplicity that all the height:s are distinct, so there are no two people of the exact same height. The algorithm returns the number of people who can see to the front of the line, in other words, the number of people in the line who are taller than everybody before them in the line. More formally, this is {i: for all j 1 For example, on input 154, 170,166,175,161,185, the algorithm would return 4, as there are four people who are taller than everyone before them, shown in bold NumCanSee(ai,..., an : list of n 2 0 distinct heights) (a) num=1 (b) max-ai (c) for i from 2 toin (d)if a, >max then nurn = nurn + 1 mac-ai g) return num (a) (4 points) Clearly state two appropriate loop invariants for NumCanSee that will help to prove the correctness of the algorithm. (Hint: The loop invariants should involve the values max and mum (b) (4 points) Prove both loop invariants using induction c) (4 points) Conclude from the loop invariant that the algorithm NumCanSee is correct (d) (4 points) Determine the runtime fo NumCanSee in Big-Theta notation