PARtition $(A,p,r)$

$,x=A[r],//$ the pivot

$,i=p-1\frac{,}{\frac{?}{?}}$ highest index into the low side

$,$for $j=p$ to $r-1,//$ process each element other than the pivot

$,,$if $A[j]x,//$ does this element belong on the low side?

$,,,i=i+1\frac{,}{\frac{?}{?}}$ index of a new slot in the low side

$,,,$exchange $A[i]$ with $A\frac{j}{\frac{?}{?}}$ put this element there

$,$exchange $A[i+1]$ with $A[r]\frac{,}{\frac{?}{?}}$ pivot goes just to the right of the low side

$,$return $i+1,//$ new index of the pivot

partition.jpg

What value would the PARTITION $($A$,1,100)$ algorithm return when all elements in the array A have the same value?

Please note that array A index is $1-$based, meaning the first element has index $1.$