3. (20 pts.) (a) Provide pseudocode for linear search. The input is an array A[1, 2, ..., n] of integers and another integer, v, which is the searched value. The output is nil if there is no array element equal to v; otherwise, it is the smallest index i such that A[i] = v. (b) Prove the correctness of your pseudocode using appropriate loop invariants and other claims. (c) Analyze the running time of your pseudocode by following the textbook's method (Section 2.2)