2. Searching the Dark Valley (15 points) A list of n distinct integers a1,a2,,an is called a valley list if the elements reading from left to right first decrease and then increase. The location of the valley is the value i where ai is 1 . For example, the list 3,2,1,6,7 is a valley list with a valley at 3 since the number 1 occurs in the third position. We also consider a list of n increasing numbers to be a valley list with a valley at 1 , and a list of n decreasing numbers to be a valley list with a valley at n. (a) (2 points) Fill in the blank for the pseudocode for an algorithm based on linear search that takes as input a valley list a1,a2,,an and returns the location of the valley. procedure LinearValley (a1,a2,,an : valley list) 1. for i:=1 to n1 2. if 3. return i 4. return n (b) (3 points) What is a loop invariant of LinearValley that you could use to prove the correctness of LinearValley? (You do not have to prove.) (c) (2 points) Fill in the blank for the algorithm based on binary search that takes as input a valley list a1,a2,,an and returns the location of the valley. procedure BinaryValley (a1,a2,,an : valley list) 1. i:=1 2. j:=n 3. while (i