Destroying balls

★★★★★

0 votes

Hiring, Open, Recruit, Hiring, Open, Recruit, Hiring, Sorting, Implementation, Advanced Sorting, Advanced sorting, Algorithms, Greedy algorithm, Easy

Details

Submissions

Discussion

Editorial

Problem

There are $N$ balls in a row. The $i^{th}$ ball has color $A_i$ . Your task is to destroy all the balls by using the following operation any number of times:

Assume that the current number of balls is $k$ . All the balls of color $k$ are destroyed at the same moment. In different scenarios, you are required to determine whether you can destroy all the balls or not.

Input format

First line: $t$ denoting the number of test cases
Each test case: An integer $N$ denoting the number of balls
Next line: $N$ space-separated integers corresponding to the color of balls

Output format
For each test case, if all the balls can be destroyed, then print $YES$ . Otherwise, $NO$ .

Constraints

$1≤ t ≤ 200$
$1≤N≤1000$
$1≤A_i≤1000000000$

Sample Input

1
6
1 3 3 6 6 6

Sample Output

YES

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Initially, there are 6 balls. Now, all balls having color equal to 6 are destroyed together at the same moment. Now, there are 3 balls remaining.

All balls having color equal to 3 are destroyed together at this moment. Now, there is only 1 ball remaining. All balls having color equal to 1 are destroyed together at this moment.

After this operation, all balls have been destroyed. Thus, the answer is yes.

Contributers:

Rachit Jain