Monk being monitor
Tag(s):

## Easy-Medium, Sorting

Problem
Editorial
Analytics

Monk being the monitor of the class needs to have all the information about the class students. He is very busy with many tasks related to the same, so he asked his friend Mishki for her help in one task. She will be given heights of all the students present in the class and she needs to choose 2 students having heights $h_1$ and $h_2$ respectively, such that $h_1 > h_2$ and difference between the number of students having height $h_1$ and number of students having height $h_2$ is maximum.

Note: The difference should be greater than 0.

As Mishki has never been a monitor of the class, help her in the same. If there exists such students, then print the required difference else print "1" (without quotes).

Input:
The first line will consists of one integer T, which denotes the number of test cases.
For each test case:
One line consists of a integer N, denotes the number of students in the class.
Second line contains N space separated integers, where $i^{th}$ integer denotes the height of the $i^{th}$ student in the class.

Output:

For each test case, if the required difference exists then print its value, otherwise print 1. Print the answer for each test case in a new line.

Constraints:
$1 \le T \le 10$
$1 \le N \le 10^5$
$1 \le height\space of \space the\space student \le 10^6$

SAMPLE INPUT
1
6
3 1 3 2 3 2
SAMPLE OUTPUT
2

Explanation

Here T=1 and N = 6.

Number of students having height = 3 is 3.
Number of students having height = 2 is 2.
Number of students having height = 1 is 1.

Here Mishki can choose students with height=3 ($h_1$) and height = 1 ($h_2$) , as the difference between number of students having height ($h_1$) and number of students having height ($h_2$) is maximum and greater than 0.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

CodeMonk (Sorting)

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting
• Algorithms > Sorting
• Algorithms > Sorting
• Algorithms > Sorting