Codeforces Round 809 (Div. 2) |
---|
Finished |
You have a sequence of $$$n$$$ colored blocks. The color of the $$$i$$$-th block is $$$c_i$$$, an integer between $$$1$$$ and $$$n$$$.
You will place the blocks down in sequence on an infinite coordinate grid in the following way.
A tower is formed by $$$s$$$ blocks such that they are placed at positions $$$(x, y), (x, y + 1), \ldots, (x, y + s - 1)$$$ for some position $$$(x, y)$$$ and integer $$$s$$$. The size of the tower is $$$s$$$, the number of blocks in it. A tower of color $$$r$$$ is a tower such that all blocks in it have the color $$$r$$$.
For each color $$$r$$$ from $$$1$$$ to $$$n$$$, solve the following problem independently:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).
The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le n$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output $$$n$$$ integers. The $$$r$$$-th of them should be the maximum size of an tower of color $$$r$$$ you can form by following the given rules. If you cannot form any tower of color $$$r$$$, the $$$r$$$-th integer should be $$$0$$$.
671 2 3 1 2 3 164 2 2 2 4 41155 4 5 3 563 3 3 1 3 381 2 3 4 4 3 2 1
3 2 2 0 0 0 0 0 3 0 2 0 0 1 0 0 1 1 1 1 0 4 0 0 0 2 2 2 2 0 0 0 0
In the first test case, one of the possible ways to form a tower of color $$$1$$$ and size $$$3$$$ is:
The blocks at positions $$$(0, 0)$$$, $$$(0, 1)$$$, and $$$(0, 2)$$$ all have color $$$1$$$, forming an tower of size $$$3$$$.
In the second test case, note that the following placement is not valid, since you are not allowed to place block $$$6$$$ under block $$$5$$$:
It can be shown that it is impossible to form a tower of color $$$4$$$ and size $$$3$$$.
Name |
---|