P8083 [COCI 2011/2012 #4] OGRADA

You are given two arrays $A, B$, each with $N$ elements. Define the weight of an array as the sum of the absolute differences of all adjacent elements in the array. You may reorder array $B$ into any permutation $B'$, such that for all $i \in [1, N) \cap \Z$: - If $A_i \lt A_{i+1}$, then $B'_i \lt B'_{i+1}$. - If $A_i \gt A_{i+1}$, then $B'_i \gt B'_{i+1}$. Find, among all valid permutations, a permutation $B'$ with the maximum weight, and output this maximum weight.

The first line contains an integer $N$. The second line contains $N$ positive integers $A_i$. The third line contains $N$ positive integers $B_i$.

The first line contains one positive integer, the maximum weight. The second line contains $N$ positive integers separated by spaces, representing the elements of $B'$. If there are multiple valid $B'$, output any one of them.

**[Sample 1 Explanation]** Valid arrays $B'$ include: - $\{1,3,2,4\}$, with weight $2+1+2=5$. - $\{1,4,2,3\}$, with weight $3+2+1=6$. - $\{2,3,1,4\}$, with weight $1+2+3=6$. - $\bf \{2,4,1,3\}$ **, with weight** $\bf2+3+2=7$. - $\{3,4,1,2\}$, with weight $1+3+1=5$. **[Constraints]** - For $100\%$ of the testdata, $2 \le N \le 3 \times 10^5$, and $1 \le A_i, B_i \lt 10^9$. **[Hints and Notes]** If you only get the first line correct but the second line is wrong or empty, you can get $50\%$ of the score for the corresponding test point. You are welcome to hack the self-written [Special Judge](https://www.luogu.com.cn/paste/xuyueqnf) via private messages or by making a post. **This problem is translated from [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_.** **The score of this problem follows the original COCI setting, with a full score of $120$.** Translated by ChatGPT 5