a) Fill in the specification of procedure FOO of Algorithm 3. The blanks are indicated by ???. Note that the output depends on t.

b) Prove that Algorithm 3 is correct.

3. The students of the University of Disciplitown usually line up in front of a small canteen to buy their lunch. They make a perfect line so a student can see what is available in the canteen only if everybody in front of them is shorter than then the heights of the students are positive integers. We model the line of students as an array of heights. For example 3, 4, 2, 4, 8 means that the student closest to canteen has height 3 the next student has height 4 and the last student in the line has height 8. The three bolded students in the array can see the canteen. Consider the specification and procedure in Algorithm 3. selves. For simplicity, we assume that Algorithm 3 Input: A list A of n positive integers with n 2 0 Output: The number of students that can see the canteen. l: procedure WHOCANSEE(A[1,... , n]) 2: return Foo(A1,... , n], 0) Input: ??? Output: ??? 3: procedure Foo(A[1,... , n],t) if n - 0 then return 0 5: 6: 7 8: 9: 10: else if h > t then return 1+ FOO(A[2,... ,n], h) else return Foo(A[2,..., n], t)