This problem is, basically, an exercise in balanced binary search trees. Specifically, given an array of length n, the problem can be solved if we can support these operations in O(logn) per operation (amortized).
1. Finding the kth element
2. Finding the location of a certain element in the array
3. Rotating the order of elements i...j
So we now try to implement each of these operations on a splay tree. How a splay tree works can be found here: http://en.wikipedia.org/wiki/Splay_tree. The reason a splay tree is best suited for this kind of work is any segment can be rotated into a single subtree (by splaying its two end points).
1. We keep a counter on each subtree of its size, then walk down the tree to
find it. Note we must splay it after finding it.
2. Splay the element up to root, and return 1 plus the size of its left
subtree.
3. On each subtree, keep a bit to indicate whether the subtree was rotated.
Then when we access, we can use 'lazy' update to make sure all the nodes we
visited are not 'flipped'. Then to rotate i..j, it suffices to splay element
i-1 up to root, the splay j+1 up so i..j are all in the same subtree. Flipping
the bit on that subtree suffices.
Each of these operations does not interfere with the splay theorem. So they all are O(logn) amortized.