题解：P13364 [GCJ 2011 Qualification] GoroSort

不妨假设策略最终排好序次数的期望存在，否则没有讨论的意义。

对于任何策略，考虑它一次对于一个排列的操作对不动点个数带来的影响。假定选取了 $m$ 个位置，其中 $p$ 个原本就是不动点，$q$ 个在排列后（这个位置）可能是不动点。根据期望的线性性，期望增加的不动点个数是 $q/m-p\le 1$。且若每次选取所有未归位的点，这个数恰好是 $1$。

直觉上每次减少不超过 $1$ 那么一定至少要这么多次才能归位，可以用鞅来严谨化这一点。

考虑令 $c_k$ 为表示 $k$ 步之后未归位的点个数，则根据上文可以验证 $d_k=c_k+k$ 是一个下鞅。定义停时 $T$ 为第一次 $c_k=0$ 的时候。（也就是排好序的时候）根据假设，$\mathbb E[T]$ 存在。并且，因为 $0\le c_k\le n$，有 $|d_k-d_{k+1}|\le n+1$ 恒成立。因此停时定理的条件成立！可以利用下鞅的停时定理得到 $\mathbb E[d_T]\ge \mathbb E[d_0]$，化简可得 $\mathbb E[T]\ge c_0$，而 $c_0$ 表示初始未归位的点的个数。特别的，在策略“每次选取所有未归位的点”中，这个下鞅是一个鞅，等式取等。因此答案为 $c_0$。

for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    print('Case #%d: %d'%(_+1,sum(a[i]!=i+1 for i in range(n))))