P8083 [COCI 2011/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 解释】** 合法的数组 $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](https://www.luogu.com.cn/paste/xuyueqnf) 进行 hack。 **题目译自 [COCI 2011-2012](https://hsin.hr/coci/archive/2011_2012/) [CONTEST #4](https://hsin.hr/coci/archive/2011_2012/contest4_tasks.pdf) _Task 4 OGRADA_。** **本题分值按 COCI 原题设置，满分 $120$。**