Problem Description

To welcome Santa Claus, the city hall has prepared $N$ Christmas trees. The officials want to arrange these trees into two rows such that in each row:

• The difference in height between adjacent trees is equal.
• The trees are arranged in ascending order of height.

Please help find a suitable arrangement.

Input Format

The first line contains an integer $N$, representing the total number of Christmas trees.

The second line contains $N$ integers, where the $i$-th integer $h_i$ represents the height of the $i$-th Christmas tree.

Output Format

The first line should output an integer $A$, representing the number of Christmas trees in the first row.

The second line should output $A$ integers, representing the heights of the trees in the first row in order.

The third line should output an integer $B$, representing the number of Christmas trees in the second row.

The fourth line should output $B$ integers, representing the heights of the trees in the second row in order.

In the provided solution, each row must have at least one tree, i.e., $A > 0, B > 0$, and every tree should be placed in one of the rows, i.e., $A + B = N$. Additionally, the trees in each row must be sorted in ascending order of height. If there are multiple solutions, output any one of them. Otherwise, output a single integer -1.

Sample Input and Output

Sample Input #1

4
1 2 3 4

Sample Output #1

2
1 2
2
3 4

Sample Input #2

6
23 4 7 6 8 15

Sample Output #2

3
4 6 8
3
7 15 23

Sample Input #3

6
1 2 3 7 9 10

Sample Output #3

-1

Notes

Data Range and Constraints

For $100\%$ of the data, $2 \le N \le 10^5, 1 \le h_i \le 10^9$.

Notes

This problem's score is set according to the original COCI contest, with a full score of $110$.

This problem uses a non-official Special Judge, and everyone is welcome to hack it (either privately or by posting).

The problem is translated from COCI2019-2020 CONTEST #3 T3 Drvca.

见题面 Input 部分

见题面 Output 部分