# [Solution] Array Balancing solution codeforces

Array Balancing solution codeforces – You are given two arrays of length 𝑛n𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an and 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn.

You can perform the following operation any number of times:

1. Choose integer index 𝑖i (1𝑖𝑛1≤i≤n);
2. Swap 𝑎𝑖ai and 𝑏𝑖bi.

## [Solution] Array Balancing solution codeforces

What is the minimum possible sum |𝑎1𝑎2|+|𝑎2𝑎3|++|𝑎𝑛1𝑎𝑛||a1−a2|+|a2−a3|+⋯+|an−1−an| ++ |𝑏1𝑏2|+|𝑏2𝑏3|++|𝑏𝑛1𝑏𝑛||b1−b2|+|b2−b3|+⋯+|bn−1−bn| (in other words, 𝑖=1𝑛1(|𝑎𝑖𝑎𝑖+1|+|𝑏𝑖𝑏𝑖+1|)∑i=1n−1(|ai−ai+1|+|bi−bi+1|)) you can achieve after performing several (possibly, zero) operations?

Input

The first line contains a single integer 𝑡t (1𝑡40001≤t≤4000) — the number of test cases. Then, 𝑡t test cases follow.

The first line of each test case contains the single integer 𝑛n (2𝑛252≤n≤25) — the length of arrays 𝑎a and 𝑏b.

The second line of each test case contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (1𝑎𝑖1091≤ai≤109) — the array 𝑎a.

The third line of each test case contains 𝑛n integers 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn (1𝑏𝑖1091≤bi≤109) — the array 𝑏b.

## [Solution] Array Balancing solution codeforces

For each test case, print one integer — the minimum possible sum 𝑖=1𝑛1(|𝑎𝑖𝑎𝑖+1|+|𝑏𝑖𝑏𝑖+1|)∑i=1n−1(|ai−ai+1|+|bi−bi+1|).

Example
input

Copy
3
4
3 3 10 10
10 10 3 3
5
1 2 3 4 5
6 7 8 9 10
6
72 101 108 108 111 44
10 87 111 114 108 100

output

Copy
0
8
218


## Array Balancing solution codeforces Note

In the first test case, we can, for example, swap 𝑎3a3 with 𝑏3b3 and 𝑎4a4 with 𝑏4b4. We’ll get arrays 𝑎=[3,3,3,3]a=[3,3,3,3] and 𝑏=[10,10,10,10]b=[10,10,10,10] with sum 3|33|+3|1010|=03⋅|3−3|+3⋅|10−10|=0.

In the second test case, arrays already have minimum sum (described above) equal to |12|++|45|+|67|++|910||1−2|+⋯+|4−5|+|6−7|+⋯+|9−10| =4+4=8=4+4=8.

In the third test case, we can, for example, swap 𝑎5a5 and 𝑏5b5.