$n$ 轮以内一定能排序：考虑形如 $x,x+1,\ldots,n$ 的后缀，这个后缀每一轮都会变长。对于剩余的前缀，我们需要将所有的前缀最大值取出来，然后将其他数翻转之后接在前面。

事实上如果我们暴力进行上述操作，需要取出的前缀最大值的总数是 $O(n)$ 的。这是因为经过若干轮操作后，数组一定形如递减段 + 中间段 + 递增段。其中中间段是从未被取出过的。每一轮过后，递增段的末尾会进入已经排序好的后缀，而取出的前缀最大值一定是递减段的开头加上中间段的一些数，然后递减段加上这些新的前缀最大值成为了新的递增段，递增段成为了新的递减段。因此我们会发现每个数进入递减或者递增段之后就会一直保持，从而取出的数总数是 $O(n)$ 的。

接下来可以用平衡树翻转直接维护，或者按照上述分析分三段维护。时间复杂度 $O((n+q)\log(n+q))$。