CF1706B.Making Towers

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.

1. Initially, you place block $1$ at $(0, 0)$.
2. For $2 \le i \le n$, if the $(i - 1)$-th block is placed at position $(x, y)$, then the $i$-th block can be placed at one of positions $(x + 1, y)$, $(x - 1, y)$, $(x, y + 1)$ (but not at position $(x, y - 1)$), as long no previous block was placed at that position.

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:

• Find the maximum size of a tower of color $r$ that you can form by placing down the blocks according to the rules.

你有一列 $n$ 个有颜色的方块。第 $i$ 个方块的颜色为 $c_i$，是一个介于 $1$ 到 $n$ 之间的整数。

你将按顺序把这些方块放置在一个无限坐标网格上，方式如下：

1. 最初，将第 $1$ 个方块放在位置 $(0, 0)$。
2. 对于 $2 \le i \le n$，若第 $(i - 1)$ 个方块被放置在位置 $(x, y)$，则第 $i$ 个方块可被放置在以下位置之一：$(x + 1, y)$、$(x - 1, y)$ 或 $(x, y + 1)$（但不能放在 $(x, y - 1)$），前提是该位置此前未被任何方块占据。

一个塔（tower） 由 $s$ 个方块构成，它们的位置为 $(x, y), (x, y + 1), \ldots, (x, y + s - 1)$，其中 $(x, y)$ 为某一起始位置，$s$ 为正整数。该塔的大小为 $s$，即其所含方块的数量。一个颜色为 $r$ 的塔 是指其中所有方块的颜色均为 $r$ 的塔。

对每个颜色 $r$（$r = 1, 2, \dots, n$），独立求解以下问题：

• 在遵守上述放置规则的前提下，你能构造出的颜色为 $r$ 的塔的最大可能大小是多少？

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$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$1 \le c_i \le n$）。

保证所有测试用例的 $n$ 值之和不超过 $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$.

对于每个测试用例，输出 $n$ 个整数。其中第 $r$ 个整数应为你能按照给定规则构造出的颜色为 $r$ 的塔的最大高度。若无法构造出任何颜色为 $r$ 的塔，则第 $r$ 个整数应为 $0$。

In the first test case, one of the possible ways to form a tower of color $1$ and size $3$ is:

• place block $1$ at position $(0, 0)$;
• place block $2$ to the right of block $1$, at position $(1, 0)$;
• place block $3$ above block $2$, at position $(1, 1)$;
• place block $4$ to the left of block $3$, at position $(0, 1)$;
• place block $5$ to the left of block $4$, at position $(-1, 1)$;
• place block $6$ above block $5$, at position $(-1, 2)$;
• place block $7$ to the right of block $6$, at position $(0, 2)$.

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$.

在第一个测试用例中，构造一个颜色为 $1$、大小为 $3$ 的塔的一种可能方式如下：

• 将方块 $1$ 放置在位置 $(0, 0)$；
• 将方块 $2$ 放置在方块 $1$ 的右侧，即位置 $(1, 0)$；
• 将方块 $3$ 放置在方块 $2$ 的上方，即位置 $(1, 1)$；
• 将方块 $4$ 放置在方块 $3$ 的左侧，即位置 $(0, 1)$；
• 将方块 $5$ 放置在方块 $4$ 的左侧，即位置 $(-1, 1)$；
• 将方块 $6$ 放置在方块 $5$ 的上方，即位置 $(-1, 2)$；
• 将方块 $7$ 放置在方块 $6$ 的右侧，即位置 $(0, 2)$。

位于位置 $(0, 0)$、$(0, 1)$ 和 $(0, 2)$ 的方块颜色均为 $1$，从而构成一个大小为 $3$ 的塔。

在第二个测试用例中，请注意以下放置方式是无效的，因为你不允许将方块 $6$ 放置在方块 $5$ 的下方：

可以证明：无法构造一个颜色为 $4$、大小为 $3$ 的塔。