[Bulgaria 2001] 

Problem: Given a permutation of the numbers 1, 2, …, n, one may interchange two consecutive blocks to obtain a new permutation. For instance, 3 5 4 8 9 7 2 1 6 can be transformed to 3 9 7 2 5 4 8 1 6 by swapping the consecutive blocks 5 4 8 and 9 7 2. Find the least number of changes required to change n, n-1, n-2, …, 1 to 1, 2, …, n. 
Solution: One way to do this would be to 
take the tail of the given descending series and start the block swapping
For eg. seq = 4321
Iteration 1: From tail, block size = 2 ^ 0 = 1
     4321
-> 4312
Interation 2 From tail, block size = 2 ^ 1 = 2
-> 1243
-> -> Repeated nested Iteration 1 1234
Similarly for 87654321
Iteration 3,  From tail, block size = 2 ^ 2 = 4
we start from above 87651234

-> Then we would get 12348765

->-> Repeat nested iteration 1 12348756

->-> ->Repeat nested iteration 2 12345678

This works well for even numbers. For odd numbers we would have one digit on the left still remaining to move over to the last. Therefore we will have to additionally swap it with one number each to the right until the last

Note that we are not able to apply the increasing subsequence dynamic programming to the above. That technique relies on the presence of an increasing subsequence in the given permutation so that those elements that participate in the increasing subsequence need not be moved at all and can remain in their positions while the others are exchanged to arrive in sequence with them.  In the above, every element is not at the  position it should be in and therefore has to move. Hence the minimum number of moves must be the length of the given sequence - 0 since there are no elements in increasing subsequence. But we are allowed to move as part of blocks. So we do this in a greedy way
The number initially moves by itself but after the first swap, it becomes part of an increasing sequence and hops the number of elements equal to the length of its current block.
Since the blocks can be formed only with the exchange of two adjacent sub-blocks, each hop is a multiple of two. This gives an increasing sequence of block lengths to hop and reduces the number of linear individual moves to the correct position.
The last element that remains is however a single element on the left that has to move all the way to the right when the sequence is odd. For this the last element the block size is unfortunately one and has to exchange positions with at most one element.

The total number of moves for any element is therefore a logarithm of the length of the sequence of elements