Codeforces Round 981 (Div. 3) |
---|
Finished |
Sakurako's exams are over, and she did excellently. As a reward, she received a permutation $$$p$$$. Kosuke was not entirely satisfied because he failed one exam and did not receive a gift. He decided to sneak into her room (thanks to the code for her lock) and spoil the permutation so that it becomes simple.
A permutation $$$p$$$ is considered simple if for every $$$i$$$ $$$(1\le i \le n)$$$ one of the following conditions holds:
For example, the permutations $$$[1, 2, 3, 4]$$$, $$$[5, 2, 4, 3, 1]$$$, and $$$[2, 1]$$$ are simple, while $$$[2, 3, 1]$$$ and $$$[5, 2, 1, 4, 3]$$$ are not.
In one operation, Kosuke can choose indices $$$i,j$$$ $$$(1\le i,j\le n)$$$ and swap the elements $$$p_i$$$ and $$$p_j$$$.
Sakurako is about to return home. Your task is to calculate the minimum number of operations that Kosuke needs to perform to make the permutation simple.
The first line contains one integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.
Each test case is described by two lines.
It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^6$$$.
It is guaranteed that $$$p$$$ is a permutation.
For each test case, output the minimum number of operations that Kosuke needs to perform to make the permutation simple.
651 2 3 4 555 4 3 2 152 3 4 5 142 3 4 131 3 272 3 1 5 6 7 4
0 0 2 1 0 2
In the first and second examples, the permutations are already simple.
In the fourth example, it is sufficient to swap $$$p_2$$$ and $$$p_4$$$. Thus, the permutation will become $$$[2, 1, 4, 3]$$$ in $$$1$$$ operation.
Name |
---|