题目描述

给定两个元素个数为 $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'$，请输出任意一种。

4
5 7 4 9
1 2 3 4

7
2 4 1 3

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

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$。

【提示与说明】

如果只答对第一行而第二行错误或为空，则可以获得对应测试点 $50\%$ 的分数。

欢迎通过私信或发帖对自行编写的 Special Judge 进行 hack。

题目译自 COCI 2011-2012 CONTEST #4 Task 4 OGRADA。

本题分值按 COCI 原题设置，满分 $120$。