4024 - [COCI 2011-2012 #4] OGRADA

给定两个元素个数为 N 的数组 A,B，且 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'，请输出任意一种。

【样例一解释】

合法的数组 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。