戳我下载下发文件。

题目描述

有 $2n$ 个人在走楼梯。

其中有 $n$ 个人在楼梯下面，他们需要上楼梯；另外 $n$ 个人在楼梯上面，他们需要下楼梯。

第 $i$ 个人上楼梯所需时间是 $a_i$，下楼梯所需时间是 $b_i$。第 $i$ 个人上/下楼梯需要等前 $i-1$ 个人上/下完才能进行。

请合理分配这 $2n$ 个人，钦定每个人是上楼梯还是下楼梯，使每个人走楼梯所需时间之和尽可能小。

形式化的，记：

构造一个长为 $2n$ 的 01 序列 $s$，满足 $s$ 中恰有 $n$ 个 $0$ 和 $n$ 个 $1$。试最小化 $\sum f_{s_i}(i)$，并构造方案。

输入格式

输入的第一行包含一个整数 $n$，表示每种类别的人数；

输入的第二行包含 $2n$ 个整数 $a_i$，分别表示第 $i$ 个人上楼梯所需时间。

输入的第三行包含 $2n$ 个整数 $b_i$，分别表示第 $i$ 个人下楼梯所需时间。

输出格式

输出的第一行包含一个整数，表示每个人所需时间之和的最小值。

输出的第二行包含 $2n$ 个整数 $s_i$，分别表示分配给每个人的类别。其中，若钦定第 $i$ 个人上楼梯，则 $s_i=0$，反之 $s_i=1$。

若存在多解，输出其中任一即可。

输入输出样例

2
1 3 2 4
2 3 1 3

8
0 0 1 1 

提示

【数据范围】

对于 $100\%$ 的数据，$1\le n\le5\times10^5$，$1\le a_i,b_i\le10^6$。

• $\text{Note A}$：$a_i=b_i$；
• $\text{Note B}$：序列 $a$ 单调递增，序列 $b$ 单调递减。