题意简述

给定一个 $1$ 到 $n$ 的排列 $p$。
若对于所有 $i$ 满足 $p_i = i$ 或 $p_{p_i} = i$，则称排列是 简单 的。
每次操作可以交换任意两个位置 $i, j$ 的值。问最少需要多少次操作，能使排列变成 简单 排列。

---

观察 1

任何一个排列可以分解为若干个不相交的循环。
例如 $[2,3,1,5,4]$ 对应的映射：

• $1 \to 2 \to 3 \to 1$ 是一个长度为 $3$ 的循环。
• $4 \to 5 \to 4$ 是一个长度为 $2$ 的循环。

读取排列后，可以在 $O(n)$ 时间内遍历所有循环。

---

观察 2

我们对“简单排列”的定义重述一下：
原定义：$p_i = i$ 或 $p_{p_i} = i$。
等价地说：

• 若 $p_i = i$，则是长度为 $1$ 的循环。
• 若 $p_{p_i} = i$，并且 $p_i \ne i$，则 $i$ 和 $p_i$ 形成一个长度为 $2$ 的循环。
  因此，简单排列等价于每个循环的长度不超过 $2$。

当我们在一个循环内交换两个元素时：

• 假设当前循环长度为 $x$。
• 交换两个不同的元素（它们属于这个循环），则原来的一个循环会分裂成 两个 循环，它们的长度之和为 $x$。

---

观察 3

对于一个长度为 $x$ 的循环，我们想把它拆成若干个长度不超过 $2$ 的循环。
每次操作可以（通过合适的交换）让循环长度减少 $2$。
操作次数为 $\lfloor \frac{x-1}{2} \rfloor$。

为什么？

• 长度为 $1$ 的循环不需要操作。
• 长度为 $2$ 的循环已经长度 $\le 2$，不需要操作。
• 长度为 $3$ 的循环：交换其中两个元素，变成 $1+2$（两个循环），需要 $1$ 次操作。$\lfloor (3-1)/2 \rfloor = 1$，正确。
• 长度为 $4$ 的循环：先操作一次，变成 $2+2$，需要 $1$ 次操作。公式：$\lfloor (4-1)/2 \rfloor = 1$，正确。
• 长度为 $5$ 的循环：先操作一次，变成 $3+2$，再对剩下的长度 $3$ 操作一次，变成 $1+2+2$，共 $2$ 次。公式：$\lfloor (5-1)/2 \rfloor = 2$，正确。

可以严格证明：每次操作最多将一个大循环中长度为 $2$ 的部分“切出来”，至少减少 $2$ 的长度，直到剩下 $\le 2$。

---

观察 4

不同循环的操作是独立的。
因为交换操作会影响元素的位置，但如果我们总是在同一个循环内部交换，它只会分裂该循环，不会影响其他循环。
因此，最终答案是所有循环的答案之和：

$$\text{answer} = \sum_{\text{每个循环}} \left\lfloor \frac{\text{len} - 1}{2} \right\rfloor $$

---

总复杂度

$O(n)$ 即可：遍历数组，标记已访问元素，计算每个循环的长度，累加 $\lfloor (len - 1) / 2 \rfloor$ 到答案。

---

示例验证

例 3：$[2,3,4,5,1]$

• 循环：$1\to2\to3\to4\to5\to1$，长度 $5$
• 操作次数：$\lfloor (5-1)/2 \rfloor = 2$ ✅

例 4：$[2,3,4,1]$

• 循环：$1\to2\to3\to4\to1$，长度 $4$
• 操作次数：$\lfloor (4-1)/2 \rfloor = 1$ ✅

例 6：$[2,3,1,5,6,7,4]$

• 循环 $1$：$1\to2\to3\to1$，长度 $3$ → $1$ 次
• 循环 $2$：$4\to5\to6\to7\to4$，长度 $4$ → $1$ 次
• 总共 $2$ 次 ✅