交换位置

交换位置

测试数据来自 nnu_contest/1177

描述

有N枚硬币,编号为1~N,按照1~N排列。某天,调皮的小邹打乱了硬币的顺序,现在请你帮忙,至少需要交换几次可以使硬币的排列顺序恢复到1~N。每次交换指的是拿起两枚硬币,然后交换他们的位置。比如有5个硬币:2 1 3 5 4 ,每次拿起2个硬币,交换它们的位置,对于这么简单的情况,显然,至少需要交换2次(1与2交换,5与4交换)就可以复位。

格式

输入格式为两行:
第一行: 一个正整数N(N<10000), 表示硬币的数目
第二行:N个正整数,用空格分开,表示硬币被打乱后的排列顺序。

输出数据为一行一个正整数,表示至少交换多少次,才能完成排序。

样例

输入样例1

5
3 1 2 5 4

输出样例1

3

输入样例2

5
5 4 3 2 1

输出样例2

2

约定

内存消耗 < 256M
用时 < 1s

提示

此题测试数据规模较小,暴力法也能过哦

信息

ID
1467
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者