# Few Different Elements SOLUTION FEWDIFF

Page Contents

### Few Different Elements SOLUTION FEWDIFF

Let’s call a sequence with length K good if there are at most K2+1 distinct elements in it. For example, the sequence (3,3,2,1,3) is good, since it contains 3≤52+1 distinct elements, while the sequence (1,4,8,8,2) is not good, since it contains 4>52+1 distinct elements.

You are given a sequence of integers A1,A2,…,AN. You may perform any number of operations (including zero) on this sequence. In one operation, you should choose one element of the sequence and replace it by any integer you choose. You want all contiguous subsequences of the resulting sequence to be good. What is the smallest number of operations you need to perform to achieve this?

Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers A1,A2,…,AN.
Output
For each test case, print a single line containing one integer ― the smallest number of operations needed to make all contiguous subsequences good.

Constraints
1≤T≤40
1≤N≤105
1≤Ai≤109 for each valid i
the sum of N over all test cases does not exceed 5⋅105
Subtask #1 (20 points): the sum of N over all test cases does not exceed 200
Subtask #2 (30 points): the sum of N over all test cases does not exceed 5,000
Subtask #3 (50 points): original constraints

Example Input
3
6
1 1 1 2 2 2
4
1 100 10000 1000000
5
1 2 3 2 1
Example Output
0
1
1
Explanation
Example case 1: All contiguous subsequences are already good.

Example case 2: For example, (1,100,10000) is not good. It is enough to change the sequence to (1,100,100,1000000), though.

Example case 3: For example, (1,2,3) is not good. It is enough to change the sequence to (1,2,1,2,1).