880072 - 排序

有N个瓶子,编号为从1到N,这N个瓶子乱序排成一排。现在想对瓶子进行从小到大排列,要求每次拿出2个瓶子进行互换,经过若干次互换后,使得瓶子按编号从小到大排序,但这样的互换方式有多种,每种互换方式的互换次数也不相同。请你通过编程计算出最少经过几次互换可以使瓶子按编号从小到大排序。第一行输入瓶子的个数N(2 <N<100),第二行输入目前瓶子编号的排序情况,输出最少经过几次互换可以使瓶子按编号从小到大排序。例如第一行输入的N为5,第二行输入N个正整数为21354,第一次拿出2和1进行互换,第二次拿出5和4进行互换,最少需要两次互换。

输入

第一行输入一个正整数N表示瓶子的个数(2<N<100) 第二行输入N个正整数,之间用一个空格分开,表示瓶子编号目前的排序情况

输出

输出最少经过几次互换可以使瓶子按编号从小到大排序

样例

输入

5
2 1 3 5 4

输出

2
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题