题目描述

给出$\red{2n(n<101)}$个自然数（数小于等于$\red{30000）}$。游戏双方分别为$\red{A}$方（计算机方）和$\red{B}$方（对奕的人）。只充许从数列两头取数。$\red{A}$先取，然后双方依次取数。取完时，谁取得的数字总和最大为取胜方；若双方相等，属于$\red{A}$胜。试问$\red{A}$方可否有必胜的策略？

输入格式

输入分两行输入，第一行一个数$\red{N}$，从第二行开始 是$\red{2N}$个整数，每个数不超过$\red{32000}$。

输出格式

输出共$\red{3}$行，第一行为取的数的最大和值，第二行和第三行分别为$\red{A、B}$所取之数，每行$\red{N}$个数，按由小到大的顺序输出，各数之间用一空格隔开。

样例

输入样例

4
7 9 3 6 4 5 2 3

输出样例

23
3 5 6 9
2 3 4 7