How can I keep track of the state of a sequence after rotating parts of it multiple times?
But the problem here is that the values of the elements do not matter,
since the rotations can change the order arbitrarily (actually, I do
not understand why they are first sorted).

You want to find an element according to its index in the list, not
its value. A way to do that is to keep with each node of the tree
the number of list elements (leaves) dominated by its left daughter.
Then very simple arithmetics will tell you at each node whether the
$n^th$ element of the list is to be found under the left or the right
daughter, and you acess it in $O(\log n)$ steps if the tree is
properly balanced.

Then the element in inserted at the beginning, which can also be done
in $O(\log n)$ steps.

Then you need to rebalance the tree when it gets unbalanced. But there
are techniques to maintain balancing.

The same should be possible with skiplist, again relying on some size
information to access by index rather than by value.