[ac42]

I am not clear why the proof is so long. By induction, the first i elements are already smaller than the A[i], so it's essentially an unoptimised version of

for i: 0..n-1 A[i] = min(A[i:n])

[areyousure]

After the first iteration of the loop (and every other one too), A[i] is the maximum of the array, not the minimum.

[ac42]

Oh crap, now I see it. Thanks!