You are given a permutation p, initially n,n-1,...,1.
At each step you can choose an adjacent inverse pair and swap them, until the permutation is sorted in increasing order.
For each 1<=i<=n-1, how many times will you swap p[i] and p[i+1]? Is there an upper bound?
I guess it's O(n), but I can't find a proof or counter-example.
