### 【转+翻译】
毕竟这是USACO的题，官方有题解，~~在这里缺席似乎不太好~~，**讲得很详细**，虽然和已有的几篇意思相近，但我还是给一下。
### 翻译+解释
首先我们思考一下，如果答案是k，**意味着什么**？ 这意味着**最后有n-k个数**没有被操作过（**没有被变更过顺序**）
**也就是说k有一个下限，也就是答案**：那**n-k个不用变更顺序的数字以外的数字**将会**插入到末尾k个**已经构建顺序的**元素中的正确的位置**中。
**例如：**$(3, 4, 5, 2, (1, 6)) \rightarrow (4, 5, 2, (1, 3, 6)) \rightarrow (5, 2, (1, 3, 4, 6)) \rightarrow (2, (1, 3, 4, 5, 6)) \rightarrow (1, 2, 3, 4, 5, 6)$
现在我们要干的，就是得到那长度为n-k的指令序列。容易发现，在队头牛的移动步数即是**未排序的牛数量-1加上后面已经建立顺序的牛中小于队头牛的数量。** 例如以上例子中，第一头牛需要移动3+1步。
每次完成这个操作后，队头的牛将会成为已经被排序的牛的一部分。**不幸的是，这个naive的算法的复杂度最差能达到 $O(N^2)$**
~~别灰心，别去看下一篇题解，还没完~~
我们可以**通过数据结构来优化**这个$N^2$玩意：**维护一个集合$S \subseteq \{1,\dots,n\}$，并可以高效地执行以下操作：**
1. 往$S$中插入$x \in \{1,\dots,n\}$
2. 对于一个$y \in \{1,\dots,n\}$，询问集合中小于y的元素个数
有很多数据结构可以解决，最简单的或许是树状数组（Fenwick tree），一种**支持单点修改，和区间查询**（问询$A_1 + \dots + A_i$)的数据结构，~~（如不会，请自行B**du)~~
_原文中稍稍对实现进行了一点解释，但我认为树状数组不用在这里多说了_
两种操作都只需要**对数级别的时间**，算法执行$O(n)$次这样的操作，**复杂度也就是$O(N \log N)$**
**对我的翻译和解释有异议和疑问，欢迎评论或私信。**
代码见后
### 原文
(Analysis by Franklyn Wang and Dhruv Rohatgi)
We first ask ourselves, if the answer is $k$, what does that entail? If the answer is $k$, this means that none of the final $n - k$ change their relative order, and that they must already be in order.
This gives a lower bound on $k$. It turns out that it also gives the answer, since we can insert the other $n - k$ numbers into their correct positions in the last numbers $k$.
For an example: $(3, 4, 5, 2, (1, 6)) \rightarrow (4, 5, 2, (1, 3, 6)) \rightarrow (5, 2, (1, 3, 4, 6)) \rightarrow (2, (1, 3, 4, 5, 6)) \rightarrow (1, 2, 3, 4, 5, 6)$
Now we need to find a sequence of instructions of length $n-k$. The first instruction is the number of unsorted cows minus one, plus the number of cows in the sorted suffix with indices smaller than the first cow's index. In the above example, the first cow needs to move $3 + 1$ spaces down the line.
After this instruction, the first cow will become part of the sorted suffix, and we recurse. Unfortunately, a naive implementation of this algorithm will take $O(N^2)$ time in the worst case.
We can speed it up with a data structure that maintains a set $S \subseteq \{1,\dots,n\}$ and performs the following operations efficiently: (1) For some $x \in \{1,\dots,n\}$, insert $x$ into $S$; (2) for some $y \in \{1,\dots,n\}$, count the number of elements of $S$ which are smaller than $y$.
There are a number of data structures which can solve this; perhaps the simplest is a Fenwick tree, which supports point updates (add $v$ to element $i$ of an array $A$) and prefix sums (given some $i$, compute $A_1 + \dots + A_i$). Inserting an element $x$ corresponds to incrementing $A_x$, and counting the elements smaller than $y$ corresponds to computing $A_1 + \dots + A_{y-1}$.
Both operations take logarithmic time, and the algorithm performs $O(N)$ such operations, for an overall time complexity of $O(N \log N)$.
```
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100100
int T[MAXN];
void inc(int i)
{
for(i++;i<MAXN;i+=(i&-i))
T[i]++;
}
int getSum(int i)
{
int c = 0;
for(i++;i>0;i-=(i&-i))
c += T[i];
return c;
}
int p[MAXN];
int main()
{
int N;
cin >> N;
for(int i=0;i<N;i++)
{
cin >> p[i];
p[i]--;
}
int j = N-1;
while(j > 0 && p[j-1] < p[j])
j--;
cout << j << '\n';
for(int i=j;i<N;i++)
inc(p[i]);
for(int i=0;i<j;i++)
{
cout << (j - 1 - i) + getSum(p[i]);
if(i < j - 1) cout << ' ';
inc(p[i]);
}
cout << '\n';
return 0;
}
```