Description

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

• The height difference between any two adjacent trees is the same.
• The Christmas trees are ordered from shorter to taller by height.

Please help them find a suitable arrangement.

Input Format

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

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

Output Format

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

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

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

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

In the output, each row must contain at least one tree, i.e. $A \gt 0, B \gt 0$, and every tree must be placed into one of the two rows, i.e. $A + B = N$. Also, the trees in each row must be listed in increasing order of height. If there are multiple valid solutions, output any one of them. Otherwise, output a single integer -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

Hint

Constraints and Notes

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

Notes

The score for this problem follows the original COCI setting, with a full score of $110$.

This problem uses an unofficial Special Judge. Hacks are welcome (you can send a private message or post directly).

Translated from COCI2019-2020 CONTEST #3 T3 Drvca.

Translated by ChatGPT 5