题目描述

为了迎接圣诞老人，市政厅已经准备了 $N$ 棵圣诞树。相关人员想要将这些树排成两排，使得每一排中：

• 相邻两树之间高度之差相等
• 圣诞树按照高度从小到大的顺序排列。

请你帮助大家找到一个合适的排列方式。

输入格式

第一行，输入一个整数 $N$，表示圣诞树的总数。

第二行，输入 $N$ 个整数，第 $i$ 个为 $h_i$，表示第 $i$ 棵圣诞树的高度。

输出格式

第一行，输出一个整数 $A$，表示第一排圣诞树的数量。

第二行，输出 $A$ 个整数，依次表示第一排各个圣诞树的高度。

第三行，输出一个整数 $B$，表示第二排圣诞树的数量。

第四行，输出 $B$ 个整数，依次表示第二排各个圣诞树的高度。

给出的方案中，每排都必须有树，即 $A \gt 0, B \gt 0$，并且每一棵树都应该放在其中一排，即 $A+B=N$。并且，每一排的圣诞树都必须按照高度从小到大排列。如果有多种方案，请输出任意一种。否则，只输出一个整数 -1。

4
1 2 3 4

2
1 2
2
3 4

6
23 4 7 6 8 15

3
4 6 8
3
7 15 23

6
1 2 3 7 9 10

-1

提示

数据范围及约定

对于 $100\%$ 的数据，$2 \le N \le 10^5, 1 \le h_i \le 10^9$。

说明

本题分值按 COCI 原题设置，满分 $110$。

本题使用非官方的 Special Judge，欢迎大家 hack（可私信或直接发帖）。

题目译自 COCI2019-2020 CONTEST #3 T3 Drvca 。