牛逼论文题，但或许也可以猜。

建图，对于逆序对 $i < j, A_i > A_j$ 连边 $i \to j$。这也叫做排列图（Permutation Graph）。则每次就是删去最多两个入度为 $0$ 的点。

对于任意 DAG，有论文给出了这样一个方法：

• 首先，找到一个特殊的拓扑序。像一般的拓扑排序那样，每次删去一个入度为 $0$ 的点并加到拓扑序中。
  但此处，如果有多个入度为 $0$ 的点，设 $N(v)$ 为 $v$ 的入边被删除的时间的集合。我们将每个 $N(v)$ 中的元素降序排列后寻找字典序最小的 $N(v)$（换句话说，尽可能早地被减小入度的 $v$），并在这一轮中选择 $v$。
• 然后，逆着拓扑序反着求答案。每次取两个在拓扑序中最靠后的，出度为 $0$ 的点删去，并加到答案的前端。

这样我们就至少获得了一个多项式时间的做法。考虑在排列图上如何优化之。

首先，计算出 $level(i)$ 表示以 $i$ 结尾的最长路。也就是以 $i$ 结尾的最长下降子序列长度。我们按照 $level(i)$ 升序处理所有点，不难发现这样和拓扑排序是等价的，且同层间没有连边。

那么，分层做，我们只需要支持对任意 $v,w$ 比较 $N(v),N(w)$ 的字典序即可。由于已经降序，所以我们事实上只需要比较 $N(v)-N(w),N(w)-N(v)$ 中的最大值。这是单点修改，矩形 $\max$，用树套树即可做到单次 $O(\log^2 n)$，总共 $O(n\log^3 n)$。

还是有点慢，但我们发现如果我们需要先求这个 3-side 矩形中点的最大 $level(i)$（这是静态的），是可以用主席树 $O(n\log n)$ 预处理 $O(\log n)$ 查询的（不过原论文好像用的是划分树状物，可能这就是学术界做法吧）。而同 $level$ 的点一定是反链，所以可以转化为区间 $\max$ 查询。这样就做到了 $O(n\log^2 n)$。

但是这似乎还是太 naive。

（似乎）可以观察到最小时间等于 $N$ 减去补图的最大匹配。进一步，有论文证明了本题的答案和补图的最大匹配是双射（具体的映射应该很好猜），那么我们对于一组最大匹配只需要一直找入度为 $0$ 的点就可以排出一个操作顺序。这是 $O(n\log n)$ 的。

而目前有论文声称可以在 $O(n\log \log n)$ 时间内计算排列图（显然排列图的补图也是排列图）的最大匹配，感觉很 nb。