| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 2048 MB | 3 | 3 | 3 | 100.000% |
Busy Beaver has $N$ favorite snack spots along the Charles River, labeled 1,ドル 2, \dots, N$. Each day, he wishes to enjoy a snack at spot $i$ during time $i$. What a perfectly optimized routine!
Unfortunately, the geese have other plans. For each index $i,ドル a goose occupies spot $a_i$ at time $i$. Busy Beaver absolutely refuses to visit the same spot as a goose, so his final schedule $p_1,p_2,\dots,p_N$ must be a permutation of 1,2,ドル\dots,N$ that satisfies $p_i \neq a_i$ for every 1ドル \le i \le N$.
Busy Beaver also wants to keep his life predictable. Among all valid schedules $p,ドル determine the minimum possible number of inversions\footnote{Recall that the number of inversions in $p$ is defined as the number of pairs $(i,j)$ with 1ドル \le i < j \le N$ and $p_i > p_j$.} $p$ can have. If no valid schedule exists, output $-1$.
The first line contains a single integer $T$ (1ドル \le T \le 3 \cdot 10^5$) representing the number of test cases.
The first line of each test case contains a single integer $N$ (1ドル \le N \le 3\cdot 10^5$).
The second line of each test case contains $N$ integers $a_1,a_2,\dots,a_N$ (1ドル \le a_i \le N$).
The sum of $N$ over all test cases does not exceed 3ドル \cdot 10^5$.
For each test case, print a single integer: the minimum possible inversion count among all permutations $p$ satisfying $p_i \ne a_i$ for all $i$. If no valid schedule exists, print $-1$.
4 3 2 3 1 4 1 2 3 4 5 1 1 1 1 1 10 1 1 1 1 1 10 10 10 10 10
0 2 -1 9
In the first test case, no position satisfies $a_i=i,ドル so Beaver can use his original routine $p=[1,2,3],ドル which has 0ドル$ inversions.
In the second test case, a valid schedule is $p=[2,1,4,3],ドル which has exactly 2ドル$ inversions.
In the third test case, spot 1ドル$ is occupied throughout the day, so that poor Busy Beaver fails to schedule. What a pity!