Paprika and Permutation
Contest: Codeforces Round 761 (Div. 2)
Difficulty rating: 1300
Tags: binary search, greedy, math, sortings

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$$$.

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 > 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.

Determine the minimum number of operations needed to make the array a permutation of integers $$$1$$$ to $$$n$$$. If it is impossible, output $$$-1$$$.

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).

Input format:
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.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$. ($$$1 \le a_i \le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
For the first test, the only possible sequence of operations which minimizes the number of operations is:

- Choose $$$i=2$$$, $$$x=5$$$. Perform $$$a_2 := a_2 \bmod 5 = 2$$$.

For the second test, it is impossible to obtain a permutation of integers from $$$1$$$ to $$$n$$$.

Example input:
4
2
1 7
3
1 5 4
4
12345678 87654321 20211218 23571113
9
1 2 3 4 18 19 5 6 7

Example output:
1
-1
4
2

Editorial:
Key observation: $$$x \bmod y < \frac{x}{2}$$$ if $$$x \ge y$$$, and $$$x \bmod y = x$$$ if $$$x < y$$$.
Notice that the bigger the $$$x$$$, the bigger the range of values that can be obtained after one $$$\bmod$$$ operation. So, intuitively, we want to assign smaller $$$a_i$$$ to smaller numbers in the resulting permutation.
However, if $$$a_i$$$ satisfies $$$1 \le a_i \le n$$$, we can just leave it there and use it in the resulting permutation (if multiple $$$a_i$$$ satisfy $$$1 \le a_i \le n$$$ and have the same value, just choose one). Let's suppose in the optimal solution, we change $$$x$$$ to $$$y$$$ and change $$$z$$$ to $$$x$$$ for some $$$z > x > y$$$ ($$$x$$$, $$$y$$$, $$$z$$$ are values, not indices). Then changing $$$x$$$ to $$$x$$$ (i.e. doing nothing) and changing $$$z$$$ to $$$y$$$ uses $$$1$$$ less operation. And, if it is possible to change $$$z$$$ to $$$x$$$, then it must be possible to change $$$z$$$ to $$$y$$$. However, if it is not possible to change $$$z$$$ to $$$x$$$, it might still be possible to change $$$z$$$ to $$$y$$$.
Therefore, the solution is as follows: Sort the array. For each element $$$i$$$ in the sorted array:
• If $$$1 \le a_i \le n$$$ and it is the first occurrence of element with value $$$a_i$$$, leave it there.
• Else, let the current least unassigned value in the resulting permutation be $$$m$$$, if $$$m < \frac{a_i}{2}$$$, we can assign the current element to value $$$m$$$ and add the number of operations by $$$1$$$. Else, output $$$-1$$$ directly.
The solution works in $$$O(n \log n)$$$.