MathDB

Given a permutation

(a_{1}, a_{1},...,a_{n})

of the numbers

1, 2,...,n

one may interchange any two consecutive "blocks" - that is, one may transform (

a_{1}, a_{2},...,a_{i}

\underbrace {a_{i+1},... a_{i+p},}_{A}

\underbrace{a_{i+p+1},...,a_{i+q},}_{B}...,a_{n})

into

(a_{1}, a_{2},...,a_{i},

\underbrace {a_{i+p+1},...,a_{i+q},}_{B}

\underbrace {a_{i+1},... a_{i+p}}_{A}

,...,a_{n})

by interchanging the "blocks"

A

and

B

. Find the least number of such changes which are needed to transform

(n, n-1,...,1)

into

(1,2,...,n)

Problem Statement