选择了第一个选左边或者右边之后，不难想到第一个选到的数所对应的另一个数一定要最后一个输出，为了达到最后一个输出，这个两边的数要分开处理，左边的数对应的都是 L，右边的数对应的都是 R。

将这两边看做两个队列 $L$ 和 $R$，首先我们感性地考虑：两边队头对应的另一个数一定比较 “远”，猜测可能是两边队列的队尾。接下来我们证明一定是队尾：

假设接下来要确定的回文子串的长度是 $l$（先前确定在答案序列中的数已在队列中删除），那么 $|L| + |R| - 2 = l - 2$，就是说除了这两个数之外的 $l - 2$ 个数都要先弹出队列，如果对应的这个数不在队尾，那么除非包括这个数弹出，弹出队列的数量达不到 $l - 2$，就是说这个数把队列卡住了。由此，队头对应的数一定是队尾，如果两个队列的队尾都没有对应的数，就说明无解。

确定队头对应的数一定是其中一个队列的队尾之后，把这个两个数从队列中删除也就不难了，只需实现两个双端队列，弹出一个队头之后把这个队尾也弹出就行了，假设队头的答案序列位置是 $k$，那么对应的队尾的位置就是 $n - k + 1$。

考虑字典序，我们优先把第一个数选为 L，并且队头也要优先考虑 L 。