1409. 交换

给你一个长度为 nn 的序列 aa,每次可以任选两个数 ai,aja_i,a_j 进行交换,问至少要交换多少次才能得到升序序列。保证序列中的数两两不相等。

输入

第一行一个整数 n (1n2×105)n \ (1 \leq n \leq 2 \times 10^5)

第二行 nn 个整数 a1,a2,...,an (0ai109)a_1,a_2,...,a_n \ (0 \leq a_i \leq 10^9)

输出

一个整数,表示答案。

样例

标准输入 复制文本
3
2 1 3
标准输出 复制文本
1
登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 210
通过 32