AT_agc014_f [AGC014F] Strange Sorting

你需要手玩一下样例，会发现这样一个事情：

• 所谓的 high 集合会一直窝在序列的末尾，而且会吸 low 集合的血，所以整个序列在 \(n\) 次操作内必然完成排序。

你再仔细思考一下就会知道：

• 第一次操作 \(n\) 必然在 high 集合里，第二次操作 \(n - 1\) 必然在 high 集合里，依次类推。且必然会从末尾到开头逐渐排序。

为什么会这样，你考虑到我第一次操作没有选 \(n - 1\) 只可能是前面有一个 \(n\)，但是在第二次操作时 \(n\) 必然被移动到最后一个位置，所以会将 \(n - 1\) 加进去，依次类推。

但是我们发现不总是要占满这些操作的，就比如说你第二次操作时 \(n - 1, n - 2\) 都被归位了，那么自然就少用一次操作。

考虑设 \(f_i\) 表示 \([i + 1, n]\) 按照如上方式排序需要的操作次数，但是我们就没有办法转移了。考虑记录一个 \(g_i\) 表示经过 \(f_i - 1\) 次操作后第一个元素是什么，发现其与 \(i, i + 1\) 会形成同构的关系，仔细分类讨论转移即可。

最后一步还是人力不可为之的。