CF2031D.Penchick and Desert Rabbit

为了挑战自己的极限，Penchick 决定在阿拉伯沙漠的正午阳光下生存！

在沿着一条线性绿洲跋涉时，Penchick 看到一只沙漠兔子正准备在一排棕榈树之间跳跃。有 $n$ 棵树，每棵树的高度为 $a_i$。

兔子可以在满足下列某一条件时，从第 $i$ 棵树跳到第 $j$ 棵树：

• 当 $j < i$ 且 $a_j > a_i$ 时：兔子可以向后跳到更高的树。
• 当 $j > i$ 且 $a_j < a_i$ 时：兔子可以向前跳到更矮的树。

对于每个 $i$（$1 \leq i \leq n$），请你求出如果兔子从第 $i$ 棵树出发，能够到达的所有树中高度的最大值。

第一行包含一个整数 $t$（$1 \leq t \leq 5 \cdot 10^5$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5 \cdot 10^5$），表示树的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$），表示每棵树的高度。

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

对于每个测试用例，输出 $n$ 个整数，第 $i$ 个整数表示如果兔子从第 $i$ 棵树出发，能够到达的所有树中高度的最大值。

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

• 如果兔子从第一棵树出发，可以跳到第三棵树，因为 $3 > 1$ 且 $1 < 2$。然后，兔子可以跳到第二棵树，因为 $2 < 3$ 且 $3 > 1$。可以证明兔子无法到达第四棵树，因此能够到达的最大高度为 $a_2 = 3$。
• 如果兔子从第四棵树出发，由于它已经在最高的树上，无需跳跃。

在第二个测试用例中，无论兔子从哪棵树出发，都可以跳到第一棵树。

在第五个测试用例中，如果兔子从第五棵树出发，可以跳到第四棵树，然后跳到第七棵树，最后到达第六棵树。因此，能够到达的最大高度为 $8$。

由 ChatGPT 4.1 翻译