C. Coloring of a Permutation
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

For the purposes of this problem, a permutation of length $$$n$$$ is an array of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$.

You are given a permutation $$$p = (p_1, p_2, \ldots, p_n)$$$ of the integers $$$1$$$ through $$$n$$$.

You are to color its elements using the minimum possible number of colors so that there is no pair of indices $$$(i, j)$$$ such that the following conditions hold at the same time:

  • $$$i \lt j$$$;
  • $$$p_i \lt p_j$$$;
  • the $$$i$$$-th and the $$$j$$$-th elements have the same color.

If there are several valid colorings with the minimum possible number of colors, find any of them.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$): the number of test cases. Then, $$$t$$$ test cases follow.

The first line of a test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$): the length of the permutation.

The second line of a test case contains $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$). It is guaranteed that each integer from $$$1$$$ to $$$n$$$ appears exactly once.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print two lines.

In the first line, print a single integer $$$k$$$ ($$$1 \leq k \leq n$$$): the minimum possible number of colors.

In the second line, print $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_i \leq k$$$), where $$$c_i$$$ is the color of the $$$i$$$-th element of the permutation. Each color from $$$1$$$ to $$$k$$$ must be used at least once. Any optimal valid coloring will be accepted.

Example
Input
3
5
3 1 4 2 5
4
4 3 2 1
3
1 2 3
Output
3
1 1 2 2 3
1
1 1 1 1
3
1 2 3