405598: GYM102006 K Tourists' Tour

Memory Limit:256 MB Time Limit:7 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

K. Tourists' Tourtime limit per test7 secondsmemory limit per test256 megabytesinputtour.inoutputstandard output

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.

Input

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 ≤ 106), the number of towers.

The second line contains n space-separated distinct integers (1 ≤ hi ≤ 109), the ith integer represents the height of the ith tower.

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

Output

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 ith integer is the color of the ith tower, and it must be between 1 and k (inclusive).

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

ExampleInput
1
5
7 1 9 5 2
Output
3
2 3 1 2 1
Note

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

加入题单

上一题 下一题 算法标签: