[COCI2011-2012#4] OGRADA

题目描述

给定两个元素个数为 $N$ 的数组 $A,B$。

规定一个数组的权值为该数组中所有相邻元素的大小差的绝对值之和。现可将 $B$ 数组变成其任意的一个排列 $B'$，使得对 $\forall i \in [1,N) \cap \Z$ 满足：

• 若 $A_i \lt A_{i+1}$，则 $B'_i \lt B'_{i+1}$。
• 若 $A_i \gt A_{i+1}$，则 $B'_i \gt B'_{i+1}$。

求在所有方案中权值最大的排列 $B'$ 及最大权值。

输入格式

第一行，一个整数 $N$。

第二行，$N$ 个正整数 $A_i$。

第三行，$N$ 个正整数 $B_i$。

输出格式

第一行，一个正整数表示最大权值。

第二行，$N$ 个用空格分开的正整数，表示 $B'$ 中的元素。如果有多种符合题意的 $B'$，请输出任意一种。

样例 #1

样例输入 #1

4
5 7 4 9
1 2 3 4

样例输出 #1

7
2 4 1 3

样例 #2

样例输入 #2

10
9 5 1 2 6 7 4 18 20 12
10 40 20 30 50 70 80 100 1000 500

样例输出 #2

3010
100 80 10 40 50 1000 20 70 500 30

提示

【样例 1 解释】

合法的数组 $B'$ 有：

• $\{1,3,2,4\}$，权值为 $2+1+2=5$
• $\{1,4,2,3\}$，权值为 $3+2+1=6$
• $\{2,3,1,4\}$，权值为 $1+2+3=6$
• $\bf \{2,4,1,3\}$ ，权值为 $\bf2+3+2=7$
• $\{3,4,1,2\}$，权值为 $1+3+1=5$

【数据规模与约定】

• 对于 $100\%$ 的数据，$2 \le N \le 3 \times 10^5$，$1 \le A_i,B_i \lt 10^9$。