# High Frequency CodeChef Solution

### We Are Discuss About CODECHEF SOLUTION

High Frequency CodeChef Solution

## High Frequency CodeChef Solution

Chef has an array A of length N.

Let F(A) denote the maximum frequency of any element present in the array.

For example:

• If A = [1, 2, 3, 2, 2, 1], then F(A) = 3 since element 2 has the highest frequency = 3.
• If A = [1, 2, 3, 3, 2, 1], then F(A) = 2 since highest frequency of any element is 2.

Chef can perform the following operation at most once:

• Choose any subsequence S of the array such that every element of S is the same, say x. Then, choose an integer y and replace every element in this subsequence with y.

For example, let A = [1, 2, 2, 1, 2, 2]. A few examples of the operation that Chef can perform are:

• [1, \textcolor{red}{2, 2}, 1, 2, 2] \to [1, \textcolor{blue}{5, 5}, 1, 2, 2]
• [1, \textcolor{red}{2}, 2, 1, \textcolor{red}{2, 2}] \to [1, \textcolor{blue}{19}, 2, 1, \textcolor{blue}{19, 19}]
• [\textcolor{red}{1}, 2, 2, 1, 2, 2] \to [\textcolor{blue}{2}, 2, 2, 1, 2, 2]

Determine the minimum possible value of F(A) Chef can get by performing the given operation at most once.

### Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• Each test case consists of two lines of input.
• The first line of each test case contains a single integer N denoting the length of array A.
• The second line contains N space-separated integers denoting the array A.

### Output Format

For each test case, output the minimum value of F(A) Chef can get if he performs the operation optimally.

### Constraints

• 1 \leq T \leq 5000
• 2 \leq N \leq 10^5
• 1 \leq A_i \leq N
• The sum of N over all test cases won’t exceed 2 \cdot 10^5.

### Sample 1:

Input

Output

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

2
3
2


### Explanation:

Test case 1: Chef cannot reduce the value of F(A) by performing any operation.

Test case 2: Chef can perform the operation [\textcolor{red}{1}, 1, \textcolor{red}{1}, 1, \textcolor{red}{1}] \to [\textcolor{blue}{2}, 1, \textcolor{blue}{2}, 1, \textcolor{blue}{2}]. The value of F(A) in this case is 3, which is the minimum possible.

Test case 3: Chef can perform the operation [1, \textcolor{red}{2, 2}, 1, 2, 2] \to [1, \textcolor{blue}{5, 5}, 1, 2, 2]. The value of F(A) in this case is 2, which is the minimum possible.

## SOLUTION

Yhaa You have done it but next? if YOU Want to Get Others Please Visit Here ScishowEngineer   Then Follow US HERE and Join Telegram.