Given an integer sequence ~a~ consisting of ~n~ elements, you need to split its elements into two subsequences ^∗, such that each element belongs to exactly one of the two subsequences, and both subsequences satisfy the alternating property.

A sequence satisfies the alternating property if the relation between every two consecutive elements always changes direction, i.e., it has one of the following forms:

or

Two consecutive equal elements are not considered valid.

A sequence with at most one element is always considered alternating.

∗ A subsequence of a sequence ~a~ is a sequence that can be obtained by deleting some elements (or no elements) from ~a~ without changing the order of the remaining elements.

Input

The first line contains an integer ~t~ ~(1 \le t \le 10\,000)~ — the number of test cases. The description of each test case is as follows:

• The first line contains an integer ~n~.

• The second line contains ~n~ integers ~a_1, a_2, \dots, a_n~ ~(-10^9 \le a_i \le 10^9)~.

The sum of ~n~ over all test cases does not exceed ~2 \cdot 10^5~.

Output

For each test case:

• If it is impossible to split, print NO.

• Otherwise, print YES on the first line. On the next line, print ~n~ integers ~c_1, c_2, \dots, c_n~.

Where:

• ~c_i = 1~ if the element ~a_i~ belongs to the first subsequence.

• ~c_i = 2~ if the element ~a_i~ belongs to the second subsequence.

Each ~c_i~ must be either ~1~ or ~2~.

If there are multiple answers, you may print any of them.

Scoring

For each test case, the score is calculated as follows:

Note that if the answer is YES, you still need to print all ~n~ numbers ~c_1, c_2, \dots, c_n~. If this sequence is invalid, the submission will be graded according to the partial score above.

The score of a subtask is the minimum score among all test cases in that subtask.

The score of the submission is the sum of the scores of the subtasks.

Sample Input 1

3
5
1 3 2 4 5
4
3 3 3 -1
6
1 5 2 7 3 8

Sample Output 1

YES
1 1 1 2 2
NO
YES
1 1 1 1 1 1

Notes

In the first test case, we can split it into:

• First subsequence: ~1, 3, 2~

• Second subsequence: ~4, 5~

In the second test case, there are three elements equal to ~3~. Since two consecutive equal elements are invalid, each subsequence can contain at most one element equal to ~3~. Since there are only two subsequences, it is impossible to split the sequence validly.

In the third test case, the entire sequence ~1, 5, 2, 7, 3, 8~ is already an alternating sequence. Note that empty sequence and sequence with a single element are also considered alternating.