Remove and Add solution codechef- You are given an array AA of NN integers. You must perform some (possibly zero) operations to make the elements of AA distinct.

Remove and Add solution codechef

You are given an array AA of NN integers. You must perform some (possibly zero) operations to make the elements of AA distinct.

In one operation, you can either:

• Remove one element from the beginning of the array AA and append any positive integer to the end.
• Or remove one element from the end of the array AA and prepend any positive integer to the beginning.

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

Input Format

Remove and Add solution codechef

• The first line contains a single integer TT — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer NN — the size of the array AA.
• The second line of each test case contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN denoting the array AA.

Output Format

For each test case, output the minimum number of operations required to make all the elements distinct.

Remove and Add solution codechef 

Constraints

• 1≤T≤1031≤T≤103
• 1≤N≤2⋅1051≤N≤2⋅105
• The sum of NN over all test cases does not exceed 2⋅1052⋅105
• 1≤Ai≤1091≤Ai≤109

Sample Input 1 

3
8
1 3 3 5 1 2 4 1
4
1 2 3 4
5
10 20 10 20 30

Sample Output 1 

4
0
2

Explanation

Remove and Add solution codechef

Test case 11: Initially A=[1,3,3,5,1,2,4,1]A=[1,3,3,5,1,2,4,1]. Consider the following sequence of operations.

• [1,3,3,5,1,2,4,1–]−→−−−−prepend6remove1[6,1,3,3,5,1,2,4][1,3,3,5,1,2,4,1_]→prepend6remove1[6,1,3,3,5,1,2,4]
• [6–,1,3,3,5,1,2,4]−→−−−−append7remove6[1,3,3,5,1,2,4,7][6_,1,3,3,5,1,2,4]→append7remove6[1,3,3,5,1,2,4,7]
• [1–,3,3,5,1,2,4,7]−→−−−−append8remove1[3,3,5,1,2,4,7,8][1_,3,3,5,1,2,4,7]→append8remove1[3,3,5,1,2,4,7,8]
• [3–,3,5,1,2,4,7,8]−→−−−−append9remove3[3,5,1,2,4,7,8,9][3_,3,5,1,2,4,7,8]→append9remove3[3,5,1,2,4,7,8,9]

All the elements of AA are now distinct. It can be shown that it is not possible in less than 44 operations.

Test case 22: No operations are required since all the elements of AA are already distinct.

SOLUTION

“Click Here“