Equalize the Array

Problem Description

You are given an array $a$ consisting of $n$ integers. In one move, you can choose a positive integer $x$, such that $x$ is one of the modes of the array, then add $1$ to each $x$ in $a$. An integer $x$ is a mode of an array $a$ if and only if $x$ appears most frequently in $a$. Note that an array may have multiple modes (e.g. $2,3$ are both the modes of $[2,2,1,3,3]$). Find out if it is possible to get an array that all elements in it are equal through several (possibly zero) such moves.

Input

The first line contains a single integer $T$ ($1\le T\le 100$), denoting the number of test cases. For each test case, the first line contains an integer $n$ ($1\le n\le 5\cdot 10^5$). The next line contains $n$ integers. The $i$-th number denotes $a_i$ ($1\le a_i\le n$). It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a string. If it is possible, output YES; otherwise, output NO.

Sample Input

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

Sample Output

YES
NO
YES

Source

2023“钉耙编程”中国大学生算法设计超级联赛（10）