Make All Distinct | Code Joint

You have an integer array $a_{1} \dots a_{N}$ with elements initially in the range $[1, N]$ ( $1 \leq N \leq 2 \cdot 1 0^{5}$ ), as well as a nonzero integer $K$ ( $- N \leq K \leq N, K \neq = 0$ ).

You may perform the following operation as many times as you'd like (possibly zero): select an index $i$ and set $a_{i} = a_{i} + K$ .

Find the minimum number of operations to make all array elements distinct.

For the first test, here is a possible sequence of two operations that makes all elements distinct.

4 1 4 1
5 1 4 1 (a_1 += 1)
5 1 4 2 (a_4 += 1)

SCORING:

Inputs 2-4: $N \leq 50$
Inputs 5-7: $N \leq 2000$
Inputs 8-10: $K = 1$
Inputs 11-13: No additional constraints.

Problem credits: Akshaj Arora, Benjamin Qi

Source: USA Computing Olympiad.

Input Format

The input consists of $T$ ( $1 \leq T \leq 10$ ) independent tests. Each test is described as follows:

The first line contains $N$ and $K$ .

The second line contains $a_{1} \dots a_{N}$ .

It is guaranteed that the sum of $N$ over all tests does not exceed $1 0^{6}$ .

Output Format

For each test, output a single line containing the minimum number of operations.

Note: The large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

Sample Input

4 4 1 4 1 4 1 4 -3 4 1 4 1 4 4 4 1 4 1 3 -1 1 1 2

Sample Output

2 4 2 1

Submit

Language