#XMOJ12797. 数列压缩

数列压缩

说明

时间限制:1 Sec 内存限制:256 MB 输入文件:compress.in 输出文件:compress.out

小明有一个长度为 $N$ 的数列 $a$,它是 $1,2,\dots,N$ 的一个排列。小明可以对数列进行如下操作:

  • 选出一对相邻的元素,满足(左边元素)$<$(右边元素),然后删除这两个元素中的任意一个。
一共执行 $N-1$ 次操作,把数列长度缩到 $1$。请判断是否可以做到;如果可以,输出一组合法操作顺序。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $a_1,a_2,\dots,a_N$。

输出格式

如果无法把数列缩成长度为 $1$,输出 No。

如果可行,第一行输出 Yes;第二行输出 $N-1$ 个用空格隔开的整数。第 $i$ 个整数代表第 $i$ 次操作删掉的数字。

多组合法方案时输出任意一组均可。

样例

样例 1

4
2 3 1 4

Yes
2 1 4

样例说明:

1. 选取相邻 (2,3)(2,3),删掉 22,数列变为 (3,1,4)(3,1,4)

2. 选取相邻 $(1,4)$,删掉 $1$,数列变为 $(3,4)$

3. 选取相邻 $(3,4)$,删掉 $4$,数列只剩 $(3)$

样例 2

5
5 4 2 3 1

No

样例说明:

一开始只有 (2,3)(2,3) 这一对满足左 &lt; 右。

- 若先删 $2$,数列变成 $(5,4,3,1)$,之后没有任何满足左 $<$ 右的相邻对,无法继续操作

- 若先删 $3$,数列变成 $(5,4,2,1)$,之后也没有满足左 $<$ 右的相邻对

因此无法缩到长度 $1$。

样例 3

6
3 6 2 5 1 4

Yes
1 5 6 2 4

数据范围

对于 15% 的数据,$N \le 100$。

对于 30% 的数据,$N \le 1000$。

对于 100% 的数据,$2 \le N \le 10^5$,$1 \le a_i \le N$,$i \neq j$ 时 $a_i \neq a_j$。