Prove the following loop invariants about the CountingSort algorithm, below Note that you do not need to prove that this algorithm is correct Input: data: array of n integers that are between 1 and r Input: n: size of data Input: r: range of data Output: permutation of data such that data[1] data[2]-... data[n] 1 Algorithm: CountingSort 2 count - Array(r) 3 Initialize count to 0 4 for i=1 to n do 5count[datali count[datalill +1 6 end 7 for i - 2 to r do 8 9 end countnE cour 10 output = Array(n) 11 for i - 1 to n do | | 14 end output[count[data[i]]=data[i] count [data[i]=count[data[ill-1 12 13 15 return output 1. Prove that countj] equals the number of times j appears in data 1..i, for every j from 1 up to r, after each iteration of the for loop in lines 4-6 2. Prove that countlj equals the number of values in data that are less than or equal to j after every iteration of the for loop in lines 7-9. Hint: first, prove that count jl is the number of times j appears in data after the loop in lines 4-6