1617C.md (2109B)
1 Source: https://codeforces.com/problemset/problem/1617/C 2 3 C. Paprika and Permutation 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Paprika loves permutations. She has an array $a_1, a_2, \dots, a_n$. She wants to make the array a permutation of integers $1$ to $n$. 22 23 In order to achieve this goal, she can perform operations on the array. In each operation she can choose two integers $i$ ($1 \le i \le n$) and $x$ ($x \gt 0$), then perform $a_i := a_i \bmod x$ (that is, replace $a_i$ by the remainder of $a_i$ divided by $x$). In different operations, the chosen $i$ and $x$ can be different. 24 25 Determine the minimum number of operations needed to make the array a permutation of integers $1$ to $n$. If it is impossible, output $-1$. 26 27 A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array). 28 29 Input 30 31 Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows. 32 33 The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$). 34 35 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$. ($1 \le a_i \le 10^9$). 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case, output the minimum number of operations needed to make the array a permutation of integers $1$ to $n$, or $-1$ if it is impossible. 42 43 Example 44 45 Input 46 47 ``` 48 4 49 2 50 1 7 51 3 52 1 5 4 53 4 54 12345678 87654321 20211218 23571113 55 9 56 1 2 3 4 18 19 5 6 7 57 ``` 58 59 Output 60 61 ``` 62 1 63 -1 64 4 65 2 66 ``` 67 68 Note 69 70 For the first test, the only possible sequence of operations which minimizes the number of operations is: 71 72 * Choose $i=2$, $x=5$. Perform $a_2 := a_2 \bmod 5 = 2$. 73 74 For the second test, it is impossible to obtain a permutation of integers from $1$ to $n$.