← 返回题目列表

Codeforces · 1706/B

B. 制作塔

中文机器翻译题面 查看原题

您有一系列 $$$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 - 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$$$ 的塔。

对于从 $$$1$$$ 到 $$$n$$$ 的每种颜色 $$$r$$$,独立解决以下问题:

- 根据规则放置方块,找出 $$$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$$$ 的塔,则第 $$$r$$$ 个整数应为 $$$0$$$。

示例

输入 #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

输出 #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

注意

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