问题1890--比赛分组

1890: 比赛分组

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

题目描述

小 C 的班级准备进行一次比赛,要求同学们两人一组,一共分成 n 组。 

通过抽签的方式进行分组,每名同学都可以抽一张带有 0 到 2*n-1 数字的卡片,卡片上的数字各不相同,最终持有的卡片上的数字为 k 和 k+1 的同学将组成一组(k 为偶数,例如 0 和 1 的同学为一组,而 3 和 4 两名同学不在一组),分到同一组的同学需要坐在一起,所以现在要进行座位交换。 

由于比赛马上就要开始了,为了有足够多的时间进行小组间的磨合,老师想通过最少的交换次数(任意有两名同学交换座位,则计录一次交换),最终让所有同组成员坐在一起。 

精通编程的小 C 立马算出了答案,请你也算一下,最少需要多少次交换可以使得所有的同组同学坐在一起。

输入

第一行,整数 n ,表示需要分成 n 组。 

第二行,输入一个从 0 开始的长度为 2 * n 个整数数组 a ,第 i 个整数为 ai ,ai 表示卡片上的数字,初始数组表示下标为 i 和 i+1 号同学初始时坐在一起,i 为偶数。

输出

一个整数,表示最少的交换次数。

样例输入 Copy

2
0 3 1 2

样例输出 Copy

1

提示

样例解析: 

样例中,让数字为 3 的同学和数字为 1 的同学交换,变成 0 1 3 2 ,这时, 0 和 1 坐一起, 3 和 2 坐一起,满足小组内同学坐一起的要求。 


数据范围: 

2 <= n <= 50。 

n 为偶数。 

0 <= ai < 2n。 

a 中所有元素不重复。

来源/分类