Tokitsukaze and Two Colorful Tapes
Contest: Codeforces Round 789 (Div. 1)
Difficulty rating: 1900
Tags: constructive algorithms, dfs and similar, graphs, greedy

Tokitsukaze has two colorful tapes. There are $$$n$$$ distinct colors, numbered $$$1$$$ through $$$n$$$, and each color appears exactly once on each of the two tapes. Denote the color of the $$$i$$$-th position of the first tape as $$$ca_i$$$, and the color of the $$$i$$$-th position of the second tape as $$$cb_i$$$.

Now Tokitsukaze wants to select each color an integer value from $$$1$$$ to $$$n$$$, distinct for all the colors. After that she will put down the color values in each colored position on the tapes. Denote the number of the $$$i$$$-th position of the first tape as $$$numa_i$$$, and the number of the $$$i$$$-th position of the second tape as $$$numb_i$$$.

For example, for the above picture, assuming that the color red has value $$$x$$$ ($$$1 \leq x \leq n$$$), it appears at the $$$1$$$-st position of the first tape and the $$$3$$$-rd position of the second tape, so $$$numa_1=numb_3=x$$$.

Note that each color $$$i$$$ from $$$1$$$ to $$$n$$$ should have a distinct value, and the same color which appears in both tapes has the same value.

After labeling each color, the beauty of the two tapes is calculated as $$$$$$\sum_{i=1}^{n}|numa_i-numb_i|.$$$$$$

Please help Tokitsukaze to find the highest possible beauty.

Input format:
The first contains a single positive integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

For each test case, the first line contains a single integer $$$n$$$ ($$$1\leq n \leq 10^5$$$) — the number of colors.

The second line contains $$$n$$$ integers $$$ca_1, ca_2, \ldots, ca_n$$$ ($$$1 \leq ca_i \leq n$$$) — the color of each position of the first tape. It is guaranteed that $$$ca$$$ is a permutation.

The third line contains $$$n$$$ integers $$$cb_1, cb_2, \ldots, cb_n$$$ ($$$1 \leq cb_i \leq n$$$) — the color of each position of the second tape. It is guaranteed that $$$cb$$$ is a permutation.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^{5}$$$.

Output format:
For each test case, print a single integer — the highest possible beauty.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
An optimal solution for the first test case is shown in the following figure:

The beauty is $$$\left|4-3 \right|+\left|3-5 \right|+\left|2-4 \right|+\left|5-2 \right|+\left|1-6 \right|+\left|6-1 \right|=18$$$.

An optimal solution for the second test case is shown in the following figure:

The beauty is $$$\left|2-2 \right|+\left|1-6 \right|+\left|3-3 \right|+\left|6-1 \right|+\left|4-4 \right|+\left|5-5 \right|=10$$$.

Example input:
3
6
1 5 4 3 2 6
5 3 1 4 6 2
6
3 5 4 6 2 1
3 6 4 5 2 1
1
1
1

Example output:
18
10
0

Editorial:
First, find the cycle directly, take out all the cycles, and then fill each cycle in the order: maximum, minimum, maximum, minimum $$$ \ldots $$$.
Note that when you encounter an odd cycle, the last one should be empty and fill in the middle value.
For example, in a ternary cycle, if the first and the second position are filled with $$$1$$$ and $$$9$$$, it can be observed that the contribution of the ternary cycle to the answer remains unchanged no matter which number between $$$2 \sim 8$$$ is filled in the middle. So this situation can be left out first, and finally fill in whatever number is left. The same to the cycles with odd sizes such as self cycles and five membered cycles, because the last number does not provide any contribution. In this way, you can directly construct a solution with the maximum $$$score$$$.
We notice that if we take out the numbers that has already been filled in each cycle and put them into a new cycled array $$$h$$$, in fact, the numbers providing contribution are only at the "peak" and "valley" points of the array. We define "peak" as the point with subscript $$$i$$$ where $$$h_{i}>h_{i-1}$$$ and $$$h_{i}>h_{i+1}$$$, and "valley" is the point with subscript $$$i$$$ where $$$h_{i}<h_{i-1}$$$ and $$$h_{i}<h_{i+1}$$$. Obviously, each "peak" will provide contribution of $$$2 \cdot h_{i}$$$, each "valley" will provide contribution of $$$-2 \cdot h_{i}$$$. For the points which are neither "peak"s nor "valley"s, they do not provide any contribution.
In order to maximize the score, we make the larger number in the permutation "peak" and the smaller number "valley". There are $$$\left \lfloor \frac{CircleSize}{2} \right \rfloor$$$ "peak"s and "valley"s for a circle with a length of $$$Circlesize$$$.
So the expression of the final answer can be derived from the summation formula of the arithmetic sequence:
Let $$$c=\sum \left \lfloor \frac{CircleSize}{2} \right \rfloor$$$, $$$N$$$ represents the size of the permutation, $$$score=2c \cdot (N-c)$$$.