#1155. [育华]图书整理

[育华]图书整理

题目名称:育华的图书整理

题目描述: 育华学校图书馆有一批图书需要整理上架。已知共有 n 本图书,每本图书都有一个唯一的编号,编号范围是从 1 到 n。现在图书管理员不小心将这些图书打乱了顺序,他每次可以交换两本图书的位置。请你编写一个程序,计算最少需要交换多少次,可以将图书按照编号从小到大的顺序排列整齐。

例如,图书的初始顺序为 3 2 1,只需要交换一次(交换 3 和 1 的位置)就可以得到正确顺序 1 2 3

输入格式: 第一行包含一个整数 n,表示图书的数量。 第二行包含 n 个整数,表示图书的初始顺序。

输出格式: 输出一个整数,表示最少需要交换的次数。

数据范围

  • 对于 30% 的数据,1n101 \leq n \leq 10
  • 对于 60% 的数据,1n5001 \leq n \leq 500
  • 对于 100% 的数据,1n50001 \leq n \leq 5000

样例输入

5
2 3 4 1 5

样例输出

3