← 返回题目列表

Codeforces · 995/B

B. 西装和领带

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

艾伦正在主持一场正式晚宴。 $$$2n$$$ 人以 $$$n$$$ 成对(情侣)的形式参加活动。经过一晚的欢乐时光后,艾伦想让每个人都排队拍一张最后的照片。 $$$2n$$$ 的人排队,但艾伦不喜欢这种排序。艾伦更喜欢每对都占据线上的相邻位置,因为这会使图片更加美观。

帮助艾伦找到他必须执行的相邻位置交换的最小次数,以使每对夫妇占据队列中的相邻位置。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$),即人数对。

第二行包含 $$$2n$$$ 整数 $$$a_1, a_2, \dots, a_{2n}$$$。对于每个 $$$i$$$ 和 $$$1 \le i \le n$$$,$$$i$$$ 恰好出现两次。如果 $$$a_j = a_k = i$$$,则意味着队列中的第 $$$j$$$ 和第 $$$k$$$ 人形成一对。

输出

输出一个整数,表示将人排成一行以使每一对占据相邻位置所需的最小相邻交换次数。

示例

输入 #1

4
1 1 2 3 3 2 4 4

输出 #1

2

输入 #2

3
1 1 2 2 3 3

输出 #2

0

输入 #3

3
3 1 2 3 1 2

输出 #3

3

注意

在第一个示例中,我们可以分两步转换 $$$1 1 2 3 3 2 4 4 \rightarrow 1 1 2 3 2 3 4 4 \rightarrow 1 1 2 2 3 3 4 4$$$ 。请注意,序列 $$$1 1 2 3 3 2 4 4 \rightarrow 1 1 3 2 3 2 4 4 \rightarrow 1 1 3 3 2 2 4 4$$$ 也适用于相同数量的步骤。

第二个示例案例已经满足约束条件;因此我们需要 $$$0$$$ 掉期。