#215515. [USACO26FEB] Make All Distinct B

You have an integer array with elements initially in the range (), as well as a nonzero integer ().

You may perform the following operation as many times as you'd like (possibly zero): select an index and set .

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

The input consists of () independent tests. Each test is described as follows: The first line contains and .

The second line contains .

It is guaranteed that the sum of over all tests does not exceed .

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

样例输入 1

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

样例输出 1

2
4
2
1

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:
• Inputs 5-7:
• Inputs 8-10:
• Inputs 11-13: No additional constraints.

Problem credits: Akshaj Arora, Benjamin Qi