← 返回题目列表

Codeforces · 125/D

D. 两个级数

中文机器翻译题面 查看原题

算术级数是这样一个非空的数字序列,其中任何两个连续数字之间的差是恒定的。这个常数称为公差。例如,数列3、7、11、15是一个等差数列。该定义意味着任何长度等于 1 或 2 的序列都是算术序列,而所有长度等于 0 的序列都是非算术序列。

给定一个不同整数 a1, a2, ..., an 的序列。您应该将其分成两个算术级数,或者发现该操作无法执行。拆分将给定序列的每个成员分配给两个级数之一,但数字的相对顺序不会改变。拆分是合并的逆操作。

输入

第一行包含一个正整数 n (2 ≤ n ≤ 30000),n 是给定序列的长度。第二行包含给定序列 a1, a2, ..., an (- 108 ≤ ai ≤ 108) 的元素。级数的元素是不同的整数。

输出

打印所需的算术级数,每行一个。进展可以按任何顺序定位。每个级数应至少包含一个数字。如果没有解决方案,则在输入文件的唯一行中打印“无解决方案”(不带引号)。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

6
4 1 2 7 3 10

输出 #1

1 2 3
4 7 10

输入 #2

5
1 2 3 -2 -7

输出 #2

1 2 3
-2 -7

注意

在第二个示例中,另一种解决方案也是可能的(数字三可以分配给第二个级数):1、2 和 3、-2、-7。