私认为这道题有一个不易证伪的假思路：考虑构造若干个段，使得每一段内任意元素所属的合法排列都包含于这个段中。设这个段内出现两次的元素的集合为 $e$，出现一次的元素为 $s$，易猜想分别将 $e,s$内部按字典序排序，然后按 $e-s-e$的顺序拼合为一段。最后按字典序排列若干段。
这个思路会被这个数据hack得体无完肤：

input
4
8 9 9 6
output
略。拿正解跑下即可

（注：我花了五六个小时各种调整、优化原做法无果才看了题解并补全之，拍出了这个数据） 奇怪的是似乎没什么人（包括很多高水平选手）投身于这个假做法中？是我的脑回路和所有选手不一样还是绝大多数人都是直奔正解写的？