#1370. [L1-8]简单题

Rhodoks 给 AquaMoon 一个长度为 $n$ 的序列 $a$，让她把 $a$ 划分为两个子序列，使它们的和相等。

但是 AquaMoon 水平不行，所以希望你能帮她完成，这样她就可以和 Rhodoks 贴贴啦！

你只需要输出其中两个子序列中的一个，由于可能有很多解，AquaMoon 希望你能使解是所有方案里字典序最小的。

某个序列的子序列是从最初序列通过去除某些元素但不破坏余下元素的相对位置（在前或在后）而形成的新序列。

考虑序列$A$与$B$， 考虑第一个在两个序列中对应元素不同的下标$i$，如果$A_i < B_i$则$A$的字典序小于$B$的字典序。 如果不存在这样的下标，即其中一个序列是另外一个序列的前缀，则短者字典序更小。

例如:

$[1,2,3] < [1,3]$

$[1,2] < [1,2,3]$

第一行一个整数 $n$ ，表示序列长度。

接下来一行 $n$ 个用空格隔开的整数 $a_1,a_2...a_n$，即这个序列。

第一行一个数字 $sum$ 表示子序列的和。

第二行为若干用空格隔开的整数，表示字典序最小的解。

样例输入

6
1 7 2 6 3 5

样例输出

12
1 2 6 3

样例解释

本样例有很多个解，所有的解分别为：

1 2 6 3
1 6 5
7 2 3
7 5

在这些解里面，字典序最小的是第一个，即 1 2 6 3

对于 $100\%$ 的数据，满足 $2 \leq n \leq 17, 1 \leq a_i \leq 10^9$

数据保证有解