← 返回题目列表

Codeforces · 2031/D

D. 彭奇克和沙漠兔

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

彭奇克致力于挑战自己的极限,挑战自己在阿拉伯沙漠的正午阳光下生存!

在沿着线性绿洲徒步旅行时,彭奇克发现一只沙漠兔正准备沿着一排棕榈树跳跃。有 $$$n$$$ 棵树,每棵树的高度用 $$$a_i$$$ 表示。

如果满足以下条件之一,兔子就可以从第 $$$i$$$ 树跳到第 $$$j$$$ 树:

- $$$j < i$$$ 且 $$$a_j > a_i$$$:兔子可以向后跳到更高的树上。
- $$$j > i$$$ 且 $$$a_j < a_i$$$:兔子可以向前跳到一棵较短的树上。

对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,确定兔子从第 $$$i$$$ 棵树开始可以到达的所有树中的最大高度。

输入

第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — 树的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — 树的高度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n$$$ 个整数。如果兔子从第 $$$i$$$ 树开始,则第 $$$i$$$ 整数应包含兔子可以到达的所有树中的最大高度。

示例

输入 #1

5
4
2 3 1 4
5
5 4 3 2 1
4
2 1 1 3
4
1 1 3 1
8
2 4 1 6 3 8 5 7

输出 #1

3 3 3 4 
5 5 5 5 5 
2 2 2 3 
1 1 3 3 
8 8 8 8 8 8 8 8

注意

在第一个测试用例中,树的初始高度为 $$$a = [2, 3, 1, 4]$$$。

- 如果兔子从第一棵树开始,它可以跳到第三棵树,$$$3 > 1$$$ 且 $$$1 < 2$$$。然后,兔子可以跳到第二棵树,$$$2 < 3$$$ 和 $$$3 > 1$$$。可以证明兔子无法到达第四棵树;因此,兔子能到达的树的最大高度是$$$a_2 = 3$$$。
- 如果兔子从第四棵树开始,它不需要跳到任何地方,因为它已经在最高的树上。

在第二个测试用例中,兔子可以跳到第一棵树,无论它从哪棵树开始。

在第五个测试用例中,如果兔子从第五棵树开始,它可以跳到第四棵树。然后兔子就可以跳到第七棵树,最后到达第六棵树。因此,兔子能到达的树的最大高度是$$$8$$$。