1)Solution always exists and his complexity <= O(n^2)

2)Try to solve the problem when the permutation is n (n-1) ... (n-left+1) 1 2 3 ... right where

left+right=n.

After O(n^2) steps you can get n 1 2 3 ... (n-1).

Then after O(n^2) steps you can get 1 2 3 ... n.

3)Try to reduce the problem to this permutation by O(n^2) steps.

4)Good to know: 1 2 3 ... t x-> 2 1 3 ... t x -> 3 1 2 4 ... t x -> 4 1 2 3 5 ... t x ->... ->

t 1 2 3 ... (t-1) x -> x 1 2 3 ... t by t steps. I call this operation "Shift(t)".

*Edited by author 26.07.2018 20:20*

simplest solution:

i=0..n-1 : while p[i] <> n do change(p[i]);