# Distinct Numbers Codechef Solution

### We Are Discuss About CODECHEF SOLUTION

Distinct Numbers Codechef Solution

## Distinct Numbers Codechef Solution ## Problem

Given an array A consisting of N distinct integers (1 \le A_i \le 2 \cdot N), we have to perform K moves. We perform the following steps in one move:

• Select an integer X such that 1 \le X \le 2 \cdot N and X \ne A_i for all i (X is not equal to any element of the current array).
• Append X to A.
• The score of this move = (\max_{1 \le i \le |A|} A_i) – X.
Note that the score is calculated after appending X. Thus, X can be the maximum element of the array as well.

For e.g. if A = [3, 1, 5] and we append X = 2 to A, then, A becomes [3, 1, 5, 2] and the score of this move is \max([3, 1, 5, 2]) – 2 = 5 – 2 = 3.

Find the maximum sum of scores we can achieve after performing exactly K moves.

### Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of multiple lines of input.
• The first line of each test case contains three space-separated integers N and K — the size of the array A and the number of moves respectively.
• The second line of each test case contains N space-separated integers A_1, A_2, \dots, A_N denoting the array A.

### Output Format

For each test case, output the maximum sum of scores we can achieve after performing exactly K moves.
It is guaranteed that it is always possible to perform K moves under the given constraints.

### Constraints

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^5
• 1 \le K \le N
• 1 \leq A_i \leq 2 \cdot N
• All A_i are distinct.
• Sum of N over all test cases does not exceed 2 \cdot 10^5.

### Sample 1:

Input

Output

3
3 1
1 3 6
2 2
1 2
3 2
1 2 5

4
1
3


### Explanation:

Test Case 1: We can perform the following move:

• Append X = 2. Score of this move = \max([1, 3, 6, 2]) – 2 = 6 – 2 = 4

Hence, the maximum total score is 4.

Test Case 2: We can perform the following moves:

• Append X = 4. Score of this move = \max([1, 2, 4]) – 4 = 4 – 4 = 0
• Append X = 3. Score of this move = \max([1, 2, 4, 3]) – 3 = 4 – 3 = 1

Hence, the maximum total score is 0+1=1.

Test Case 3: We can perform the following moves:

• Append X = 4. Score of this move = \max([1, 2, 5, 4]) – 4 = 5 – 4 = 1
• Append X = 3. Score of this move = \max([1, 2, 5, 4, 3]) – 3 = 5 – 3 = 2

Hence the maximum total score is 1+2=3. ## Distinct Numbers Codechef Solution

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here JOIN NOW 