Help me with this exercise by proving and explaining the answer.

Gnome Sort is a simple sorting algorithm that works by comparing adjacent elements and

moving an element to its correct position much like how a garden gnome sorts flower pots.

It is similar to insertion sort but uses a different mechanism for moving elements. Use the

loop invariant technique to prove its correctness.

Input: A $($array of integers$),$ n $($size of the array$)$

Output: Sorted array A in non$-$decreasing order

Algorithm GnomeSort$($A$,$ n$)$

pos$=1$

while pos