要求出字典序最小的方案，可以从最高位开始填数，每次尽量填 0 0 0 即可。
然后就是根据前面的情况判断能否找到合法的后缀。
设 X X X 的当前最大值为 v 1 v_1 v1，有 c 1 c_1 c1 个 high 数， Y Y Y 的当前最大值为 v 2 v_2 v2，有 c 2 c_2 c2 个 high 数。
显然原来序列中的 high 数一定会被统计，设 X , Y X,Y X,Y 之后的 high 数序列为 A , B A,B A,B。
那么有 ∣ A ∣ + c 1 = ∣ B ∣ + c 2 |A| + c_1 = |B| + c_2 ∣A∣+c1=∣B∣+c2
有一个结论是 ∣ A ∣ , ∣ B ∣ |A|,|B| ∣A∣,∣B∣ 中至少有 1 1 1 个其中的数全部为原来序列的 h i g h high high 数，不妨设为 A A A。
可以通过 A , B A,B A,B 同时删去一个非原序列的 high 数即可证明。
那么设 A , B A,B A,B 共有 s u m sum sum 个原序列的 high 数
c 1 + s u m − b = ∣ B ∣ − b + b + c 2 c_1 + sum - b = |B| - b + b + c_2 c1+sum−b=∣B∣−b+b+c2
c 1 − c 2 + s u m = ( ∣ B ∣ − b ) + 2 b c_1 - c_2 + sum = (|B| - b) + 2b c1−c2+sum=(∣B∣−b)+2b
于是需要判断后缀中选出一个递增序列 B B B，使得将其中原序列 high 数设为 2 2 2，其余 high 数设为 1 1 1，和为 c 1 − c 2 + s u m c_1 - c_2 + sum c1−c2+sum。
可以发现如果存在 k + 2 k + 2 k+2，则一定存在 k k k，于是只需要记录每个后缀的奇偶的最大值即可。
可以用主席树来存。