In 1 step, all decreasing substrings are reversed or only one?
If I have 5 6 3 4 1 2 (only 5,6 or any other such combo is reversed or all decreasing substrings are reversed in first step)
Got it. I didn't read that you mentioned "every permutation has a decomposition of decreasing substrings"

Reverse all decreasing substrings for once. After that, maximum length of decreasing substring will be 2. For all indices i we can calculate how many j are there such that j < i and a[j] > a[i]. Maximum of this value equals how many steps we need. Maximum value can be N - 1(actually N - 2 because of first step). So after N steps, permutation will be sorted.

The problem is here: http://hsin.hr/coci/archive/2011_2012/contest1_tasks.pdf and the solution here: http://hsin.hr/coci/archive/2011_2012/contest1_solutions.zip, I hope it helps you..

Yes. Short proof: number 1 moves to the left. EDIT: missed the "after N steps" part, I'll think about it.

It seems the problem is correct even for N - 1 steps. I have an idea how to solve it, but I haven't managed to turn it into the solution. Let us call a potential of a number: 0, if the number is already at its destination point; (distance from its destination)+(the length of maximal increasing sequence from number to its destination) otherwise. As an example, evolution of a sequence is below (potentials are under the numbers). The potential of '7' in the first row of example below is 6, because it is a distance from the place of 7 to 7-th place, and "71" is not an increasing sequence. The potential of '2' is 1, as distance from destination is 1, and "12" is increasing, so '1' gives additional potential. The potential of '8' is 3, because dist=2, and '9' gives additional point, as "89" is increasing, however, "895" is not increasing, so there is only 1 additional point. The potential of '6' is 2, because dist=1, and "68" increases, which gives additional 1. "689" also increases, but '9' is already beyond the destination of 6, and it doesn't counts. Another example: the potentials of "56781234" are "76544567".

712468953
612023236
---------
172468359
051022440
---------
127463859
004013130
---------
124736589
002320200
---------
124375689
001121200
---------
123457689
000001100
---------
123456789
000000000

It is easy to see that the potential cannot be greater than N - 1. My conjecture is that the maximal potential decreases every turn, and the problem follows from it. But it is not so easy to prove or disprove:/ I suppose I could give a rather technical proof, if it is actually true, after thinking a bit more.