Please do problem3

In this problem, we are given a sequence a_1, a_2, ..., a_n of integers and we want to return a list of all terms in the sequence that are greater than the sum of all previous terms of the sequence. For example, on an input sequence of 1, 4, 6, 3, 2, 20, the output should be the list 1, 4, 6, 20. The following algorithm solves this problem. procedure PartialSums(a_1, a_2, ..., a_n: a sequence of integers with n greaterthanorequalto 1) total:= 0 Initialize an empty list L. for i:= 1 to n if a_i > total Append a_i to list L. total:= total + a_i return L Prove the following loop invariant by induction on the number of loop iterations: Loop Invariant: After the i^th iteration of the for loop, total = a_1 + a_2 + ... + a_t and L contains all elements from a_1, a_2, ..., a_t that are greater than the sum of all previous terms of the sequence. Use the loop invariant to prove that the algorithm is correct, i.e., that it returns a list of all terms in the sequence that are greater than the sum of all previous terms of the sequence