Consider the following variant of the linear$-$search algorithm:

Linear$-$Search$($A$[1..$n$],$ x$)$

for i to length$[$A$]$ do:

if x $=$ A$[$i$]$

return i

return NIL

where the input array A contains n numbers and x is some number.

Prove the algorithm$$s correctness using the method of loop invariants. You must clearly state your loop

invariant, and show that it satisfies the initialization, maintenance, and termination requirements.