Consider the following algorithm for calculating the cumulative sums of an array. The input is an array

of numbers, A$.$ The output is a new array of number of the same length, R$.($Array indexes start at $1.)$

Algorithm $2$ CumulativeSums $(A)$

Rlarr new array length $[A]$

if length $[A]>0$ then

$R[1]larrA[1]$

end if

for jlarr$2$ to length $A$ do

$R[j]larrR[j-1]+A[j]$

end for

return $R$

The correctness property for this algorithm is the following:

$R[n]={\displaystyle \underset{i=1}{\overset{n}{}}}A[i],$ for all $1n$length$[A]$

$($a$)$ State the loop invariant for the for loop.

$($b$)$ Prove the correctness of the algorithm using the loop invariant.

$($c$)$ What is the running time of this algorithm? Justify your answer.