405598: GYM102006 K Tourists' Tour

The mayor is preparing for the arrival of the ICPC participants. On their tour, they will pass by n towers, each with a distinct height.

The architects designed these towers in a special way. The towers are aligned in a single line and numbered from 1 to n from left to right. Each of them is connected by a bridge to the closest tower to its left with a greater height, if one exists, and also by another bridge to the closest tower to its right with a greater height, if it exists.

The mayor doesn't want to make their tour boring. Therefore in preparation, he wants to color the n towers such that there is no bridge that connects two towers of the same color.

Help the mayor find a valid way to color the n towers with the minimum number of colors.

The first line of input contains a single integer T (1 ≤ T ≤ 128), the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 10⁶), the number of towers.

The second line contains n space-separated distinct integers (1 ≤ h_i ≤ 10⁹), the i^th integer represents the height of the i^th tower.

The sum of n over all test cases doesn't exceed 5 × 10⁶.

For each test case, output two lines. The first line should contain the minimum number of colors k needed to color the towers.

The second line should contain n space-separated integers that represent a valid way to color the towers. The i^th integer is the color of the i^th tower, and it must be between 1 and k (inclusive).

If there are multiple valid ways, print any of them.

1
5
7 1 9 5 2

3
2 3 1 2 1

In the first sample test, the pairs of towers connected by bridges are: (1, 2), (1, 3), (2, 3), (3, 4), and (4, 5).