彭奇克致力于挑战自己的极限,挑战自己在阿拉伯沙漠的正午阳光下生存!
在沿着线性绿洲徒步旅行时,彭奇克发现一只沙漠兔正准备沿着一排棕榈树跳跃。有 $$$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$$$。