题目描述
为了迎接圣诞老人,市政厅已经准备了 $N$ 棵圣诞树。相关人员想要将这些树排成两排,使得每一排中:
- 相邻两树之间高度之差相等
- 圣诞树按照高度从小到大的顺序排列。
请你帮助大家找到一个合适的排列方式。
输入格式
第一行,输入一个整数 $N$,表示圣诞树的总数。
第二行,输入 $N$ 个整数,第 $i$ 个为 $h_i$,表示第 $i$ 棵圣诞树的高度。
输出格式
第一行,输出一个整数 $A$,表示第一排圣诞树的数量。
第二行,输出 $A$ 个整数,依次表示第一排各个圣诞树的高度。
第三行,输出一个整数 $B$,表示第二排圣诞树的数量。
第四行,输出 $B$ 个整数,依次表示第二排各个圣诞树的高度。
给出的方案中,每排都必须有树,即 $A \gt 0, B \gt 0$,并且每一棵树都应该放在其中一排,即 $A+B=N$。并且,每一排的圣诞树都必须按照高度从小到大排列。如果有多种方案,请输出任意一种。否则,只输出一个整数 -1
。
样例 #1
样例输入 #1
4
1 2 3 4
样例输出 #1
2
1 2
2
3 4
样例 #2
样例输入 #2
6
23 4 7 6 8 15
样例输出 #2
3
4 6 8
3
7 15 23
样例 #3
样例输入 #3
6
1 2 3 7 9 10
样例输出 #3
-1
提示
数据范围及约定
Subtask | 分值 | 数据范围及约定 | 特殊性质 |
---|---|---|---|
$1$ | $20$ | $N \le 15$ | 无 |
$2$ | $30$ | $N \le 300$ | 无 |
$3$ | $30$ | $N \le 10^5$ | 有一种方案,使得两排圣诞树数量相等 |
$4$ | $30$ | 无 | 无 |
对于 $100\%$ 的数据,$2 \le N \le 10^5, 1 \le h_i \le 10^9$。