题目描述

你有一个长度为 $n$ 的彩色方块序列。第 $i$ 个方块的颜色为 $c_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)$），且不能放在之前已经有方块的位置。

一座“塔”由 $s$ 个方块组成，这些方块被放在 $(x, y), (x, y+1), \ldots, (x, y+s-1)$ 这些位置上，其中 $(x, y)$ 是某个位置，$s$ 是整数。塔的大小为 $s$，即其中方块的数量。颜色为 $r$ 的塔指的是所有方块颜色均为 $r$ 的塔。

对于每种颜色 $r$（$1$ 到 $n$），请独立解决如下问题：

• 按照上述规则放置方块，能形成的颜色为 $r$ 的塔的最大大小是多少？

输入格式

第一行包含一个整数 $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$。

输出格式

对于每个测试用例，输出 $n$ 个整数。第 $r$ 个数表示按照题目规则能形成的颜色为 $r$ 的塔的最大大小。如果无法形成颜色为 $r$ 的塔，则输出 $0$。

说明/提示

在第一个测试用例中，形成一个颜色为 $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$ 的塔。

由 ChatGPT 4.1 翻译

样例

6
7
1 2 3 1 2 3 1
6
4 2 2 2 4 4
1
1
5
5 4 5 3 5
6
3 3 3 1 3 3
8
1 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