Prove the following koop Invariauts 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: : size of dato Input: r: range of data Output: permutation of data such that data data S detn) Algorithm: CnntingSort a Initialize cont to 0 4 for 1 to n do e end T for j 2 to r do s count count end 0 output = Array() 11 for i 1 to n do 1 outpetcoundat-data count!data[i] = count!data(I|-1 return octput 1. Prove that count i equals the mumber of times j appears in data 1i], for every from 1 up to r, after each iteration of the for loop in lines 4-6 2. Prove that countl equals the namber of values in data that are less than or equal to j after every iteration of the or loop in es 7-9. Hint: first, prove thatut is the number of times j appears in data after the loop in lines 4-6