题解：困牛排序

算法思路

注意到最优解的形式一定为：找到原数列最长的单调上升连续后缀（即后缀中恰好是连续的若干个整数，且按升序排列）。那么需要进行操作的数就是这个后缀之前的所有数。
把这个后缀存入一个 $vector$ ，然后把前面的数按照顺序插入这个 $vector$ ，同时维护单调性。但是 $vector$ 的插入操作是单次 $O(n)$ 的，所以考虑用树状数组，每次查询 $vector$ 中比当前位置小的数量，可以优化单次到 $O(\log n)$ 。
注意每次查询时除了在树状数组中的查询结果之外，还要加上前缀中的剩余元素，因为操作剩余前缀时当前元素会对应前移。

代码实现

#include <iostream>
using namespace std;

const int N = 100005;
int n, m, a[N];
int t[N];  // 树状数组

// 树状数组：单点增加
void add(int x) {
    for(; x <= n; x += x & -x) t[x]++;
}

// 树状数组：前缀和查询
int ask(int x) {
    int res = 0;
    for(; x; x -=x & -x) res += t[x];
    return res;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    // 找到最长的单调上升后缀
    for(int i = 1; i <= n; i++) 
        if(a[i] < a[i - 1]) {  // 发现逆序，前缀结束
            m = i - 1;
        }

    cout << m << '\n';  // 输出操作次数
    
    // 将后缀元素加入树状数组
    for(int i = m + 1; i <= n; i++) add(a[i]);
    
    // 处理前m个元素
    for(int i = 1; i <= m; i++) {
        // 移动步数 = 查询值小于a[i]的元素个数 
        //         + 还需要移动的前缀元素个数
        int k = ask(a[i] - 1) + (m - i);
        cout << k << ' ';
        
        // 将当前元素加入树状数组（相当于移动到后面）
        add(a[i]);
    }
    
    return 0;
}