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]);