Problem Description

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.

Input Format

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

Output Format

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.

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

Hint

[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 via private messages or by making a post.

This problem is translated from COCI 2011-2012 CONTEST #4 Task 4 OGRADA.

The score of this problem follows the original COCI setting, with a full score of $120$.

Translated by ChatGPT 5