题目内容

给定一个数列 $\{a_n\}$ ，这个数列满足 $a_i \neq a_j(i \neq j)$ ，现在要求你把这个数列从小到大排序，每次允许你交换其中任意一对数，请问最少需要几次交换？

输入格式

从文件 $sort.in$ 中读入数据。

第一行，正整数 $n$ 。

接下来，一共 $n$ 个数，用空格分隔开，表示数列 $\{a_n\}$ 。

输出格式

输出答案到文件 $sort.out$ 中。

只有一行，包含一个数，表示最少的交换次数。

样例

样例输入

8
8 23 4 16 77 -5 53 100

样例输出

5

手动模拟可以发现最少需要 $5$ 次。

数据范围与提示

对于 $100\%$ 的数据，有 $n \le 10^5 , -2^{31} \le a_i \le 2^{31}$ 。

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$256\mathrm{MB}$

大样例下载