Interchanging consecutive subsequences to reverse $1,2,3,\ldots,n$ Here is a problem I found on Google Plus.
Given a sequence $1,2,....,n$ you are allowed to interchange any two consecutive subsequences in it. Find the least number of steps in which you can reach $n,n-1,.....,1$ using this transformation. Consecutive subsequences means the last element of the first subsequence is less than  the first element of the second subsequence.
Examples: $$12345 \to 34125 \to 32541 \to 54321$$
So, $T(5)=3$. Some other example are: $T(15)=11, T(13)=9, T(10)=7$
It has been found that, the transformation can always be done in at most $n-1$ ways by starting with $1,2,\ldots,n-1,n\to n,1,2...,n-1$ and then using induction. 
Is there a simple formula or method for finding the smallest number of ways instead of brute force?
 A: This might not be optimal, but here's a better bound.
Starting with 
$1,2,\ldots,n$ interchange 
$
1,2,\ldots,a,b,\ldots,n \rightarrow b,\ldots,n,1,\ldots\,a
$
then reverse each of $[b\ldots n]$ and $[1\ldots a]$ in the optimal way.
If we can do each part in $T(k)\le rk-1$ for some $r<1$ then
$$
T(n) \le 1+T(n-a)+T(a) \le 1+r(n-a)-1+ra-1 = rn-1
$$
Since $T(5)=(4/5)\times 5-1$ we can bound $T(5k)\le 4k-1$ for all $k\ge 1$, and since $T$ must be nondecreasing, $T(n)\le 4\lceil\frac{n}{5}\rceil-1$ for all $n>0$. (This can be made marginally better by solving directly for $T(6),T(7),T(8),T(9)$.)
Given a permutation call an ordered pair of consecutive entries $(a,b)$ upward if $a<b$. Then if we transform a general sequence
$$x_1,x_2,\ldots,x_i,y_1,\ldots\,y_j,z_1,\ldots,z_k,w_1,\ldots,w_l$$
by one interchange to 
$$x_1,x_2,\ldots,x_i,z_1,\ldots,z_k,y_1,\ldots\,y_j,w_1,\ldots,w_l$$
then the number of upward pairs can decrease by at most 2, only if
two of $z_1<x_i<y_1$, $y_1<z_k<w_1$ and $w_1<y_j<z_1$ are true (all three cannot be simultaneously true). Since the initial sequence $1,2,\ldots,n$ has $n-1$ upward pairs and the final sequence must have zero, $T(n)\ge \lceil \frac{n-1}{2}\rceil$.
So $\lceil \frac{n-1}{2}\rceil \le T(n) < 4\lceil\frac{n}{5}\rceil$ for all $n>0$.
