← 返回题目列表

Codeforces · 1677/C

C. 时风和两条彩色胶带

中文机器翻译题面 查看原题

时风有两条彩色胶带。有 $$$n$$$ 种不同的颜色,编号为 $$$1$$$ 到 $$$n$$$,每种颜色在两个磁带上只出现一次。将第一个磁带的第 $$$i$$$ 位置的颜色表示为 $$$ca_i$$$,将第二个磁带的第 $$$i$$$ 位置的颜色表示为 $$$cb_i$$$。

现在 Tokitsukaze 想要为每种颜色选择一个从 $$$1$$$ 到 $$$n$$$ 的整数值,所有颜色都是不同的。之后,她将记下胶带上每个颜色位置的颜色值。将第一个磁带的第 $$$i$$$ 个位置的编号表示为 $$$numa_i$$$,将第二个磁带的第 $$$i$$$ 个位置的编号表示为 $$$numb_i$$$。

例如,对于上图,假设红色的值为 $$$x$$$ ($$$1 \leq x \leq n$$$),它出现在第一盘磁带的 $$$1$$$-st 位置和第二盘磁带的 $$$3$$$-rd 位置,因此 $$$numa_1=numb_3=x$$$。

请注意,从 $$$1$$$ 到 $$$n$$$ 的每种颜色 $$$i$$$ 应该具有不同的值,并且出现在两个磁带中的相同颜色具有相同的值。

标记每种颜色后,两条胶带的美度计算为 $$$$$$\sum_{i=1}^{n}|numa_i-numb_i|.$$$$$$

请帮助时风找到最高的美丽。

输入

第一个包含一个正整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

对于每个测试用例,第一行包含一个整数 $$$n$$$ ($$$1\leq n \leq 10^5$$$) — 颜色数量。

第二行包含 $$$n$$$ 整数 $$$ca_1, ca_2, \ldots, ca_n$$$ ($$$1 \leq ca_i \leq n$$$) — 第一个磁带每个位置的颜色。保证 $$$ca$$$ 是一个排列。

第三行包含 $$$n$$$ 整数 $$$cb_1, cb_2, \ldots, cb_n$$$ ($$$1 \leq cb_i \leq n$$$) — 第二个磁带每个位置的颜色。保证 $$$cb$$$ 是一个排列。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^{5}$$$。

输出

对于每个测试用例,打印一个整数 - 尽可能高的美感。

示例

输入 #1

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

输出 #1

18
10
0

注意

第一个测试用例的最优解如下图所示:

美丽的是$$$\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$$$。

第二个测试用例的最优解如下图所示:

美丽的是$$$\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$$$。