P7205 [COCI 2019/2020 #3] Drvca

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.

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.

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`.

#### Constraints and Notes | Subtask | Score | Constraints and Notes | Special Property | | :----------: | :----------: | :----------: | :----------: | | $1$ | $20$ | $N \le 15$ | None | | $2$ | $30$ | $N \le 300$ | None | | $3$ | $30$ | $N \le 10^5$ | There exists a solution where the two rows have the same number of trees. | | $4$ | $30$ | None | None | 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](https://www.luogu.com.cn/paste/c2638vjq). Hacks are welcome (you can send a private message or post directly). **Translated from [COCI2019-2020](https://hsin.hr/coci/archive/2019_2020/) [CONTEST #3](https://hsin.hr/coci/archive/2019_2020/contest3_tasks.pdf) _T3 Drvca_.** Translated by ChatGPT 5