题目描述

译自 COCI 2019/2020 Contest #3 T3「Drvca」

给出一个长度为 $N$ 的序列 $h_1, h_2, \dots, h_N$。你需要把它划分成两个非空的子序列，使得每个子序列里的数构成了一个等差数列。

输入格式

第一行包含一个整数 $N$ ($2 \le N \le 10^5$)，表示序列的长度。

第二行包含 $N$ 个整数 $h_1, h_2, \dots, h_N$ ($1 \le h_i \le 10^9$)，表示给出的序列。

输出格式

第一行输出一个整数 $A$，表示第一个子序列的长度。第二行输出 $A$ 个整数，表示第一个子序列。

第三行输出一个整数 $B$，表示第二个子序列的长度。第四行输出 $B$ 个整数，表示第二个子序列。

输出的序列必须非空，也就是 $A > 0$ 和 $B > 0$。原序列里每个元素恰好也属于其中一个子序列，也就是 $A + B = N$。子序列里的元素必须按照从小到大排好序后输出。如果有多组合法方案，你可以输出任意一个。如果找不到任何方案，你仅需要输出 $-1$。

4
1 3 2 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

数据范围与提示

子任务 1（10 分）：$2 \le N \le 15$；

子任务 2（30 分）：$2 \le N \le 300$；

子任务 3（30 分）：$2 \le N \le 10^5$，存在一组解满足 $A = B$；

子任务 4（30 分）：没有额外限制。