2. [10 points] The following is a pseudocode of Insertion-sort. We would like to prove its correctness via loop invariant. Write down a loop variant. Complete the proof using Initial ization, Maintenance, Termination. INSERTION-SORT(A) l for j = 2 to A.length 3 IInsert Alj] into the sorted key = AU] sequence A[1 .. j-u i=j-1 5 while i>0 and A> key Al 11 A 7 8 A[i +1]=key Sol. Loop invariant (5pts), inti. (1pt). Maintenance (3pts). Termination (Ipt)