直接输出约分后的分母即可。
这玩意看起来就不用很多次，如果本来就是有序的那么就是 \(0\)，如果 \(a_1=1\) 或 \(a_n=n\) 那么显然只用 \(1\) 次。如果 \(a_n=1\) 且 \(a_1=n\) 那么显然需要 \(3\) 次，否则 \(2\) 次即可。
容易发现这东西和国际象棋里黑白象是类似的，奇数位置的不会和偶数位置的相撞，那么只用考虑奇偶性相同的点。然后只用使用一个栈来维护向右的点，如果只有一个向左的点在 \((x,0)\)，我们可以把其看成一个在 \((-x,0)\) 的向右的点。最后再处理剩下所有向右的点，两两配对即可。
贪心是不对的，可以找到反例。这个时候看到数据范围我们想到dp，设 \(f_i\) 代表前 \(i\) 部分的答案，那么显然有 \(f_i=min(f_j+w(j+1,i))\)，其中必须满足所有 \(1\) 都被 \(0\) 匹配，而 \(0\) 可以多于。接下来考虑计算 \(w(j+1,i)\)，可以贪心计算，把最后的 \(1\) 与最后的 \(0\) 匹配即可。
根据期望的线性性我们只用考虑每个点的期望次数，即其概率。正难则反，考虑出现不了的概率。把所有可以使其出现的城市找出来，每次可以选一段后缀，将可以选的位置数乘起来，剩下的随便选，于是就做完了。
今天晚上补
Educational Codeforces Round 109
原文：https://www.cnblogs.com/zcr-blog/p/14776561.html