SP5182 PAIRSORT - Double Sorting

这是一个典型的问题：有 $n$ 个球和 $n$ 个盒子，每个球都有一个从 $1$ 到 $n$ 的唯一编号。起初，每个盒子里各有一个球。我们可以交换相邻盒子里的两个球，从而按升序对这些球进行排序，即把编号为 $1$ 的球放到第一个盒子里，编号为 $2$ 的放到第二个盒子里，以此类推。问题是需要进行多少次交换？ 现在考虑一种稍微复杂的情况：球的数量翻倍，变成了 $2n$ 个，但盒子仍然是 $n$ 个。对于每个 $1 \le k \le n$，有两个球都编号为 $k$，并且每个盒子里放有两个球。我们只能交换相邻盒子里的两个球，每次从每个盒子里各取一个。最终目标是让两个编号为 $1$ 的球都出现在第一个盒子里，两个编号为 $2$ 的球在第二个盒子里，以此类推。还是那个问题：需要多少次交换？ 这里有一个有趣的事实。对 `[5, 4, 3, 2, 1]`（即第一个盒子中有 $5$，第二个盒子里有 $4$，以此类推）的排序需要进行 $10$ 次交换：先交换 $5$ 和 $4$，再依次交换 $5$ 和 $3$、$5$ 和 $2$、$5$ 和 $1$、$4$ 和 $3$、$4$ 和 $2$、$4$ 和 $1$、$3$ 和 $2$、$3$ 和 $1$，最后是 $2$ 和 $1$。那么，要把 `[5, 5; 4, 4; 3, 3; 2, 2; 1, 1]`（即每个盒子里有两个相同编号的球，如第一个盒子有两个 $5$）排序，需要几次交换呢？有些人可能会以为需要 $20$ 次，但实际上只需要 $15$ 次。 请编写一个程序，用来计算双球版本的最少交换次数，并验证上述结论。

输入包含以下内容： ``` n ball1,1 ball1,2 ball2,1 ball2,2 ... balln,1 balln,2 ``` 其中，$n$ 为盒子数量（$1 \le n \le 8$）。对于每个 $1 \le i \le n$，ball $_{i,1}$ 和 ball $_{i,2}$ 是起初在第 $i$ 个盒子里的两个球的编号。

输出最少可能的交换次数。 **本翻译由 AI 自动生成**