# [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β|3β3|+3β|10β10|=03β|3β3|+3β|10β10|=0.

In the second test case, arrays already have minimum sum (described above) equal toΒ |1β2|+β―+|4β5|+|6β7|+β―+|9β10||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.