# Remove and Add solution codechef

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

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

• 1T1031≤T≤103
• 1N21051≤N≤2⋅105
• The sum of NN over all test cases does not exceed 21052⋅105
• 1Ai1091≤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


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