D. Пенчик и пустынный кролик
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пенчик бросил себе вызов — выжить под полуденным солнцем в Аравийской пустыне!

На линейном оазисе в ряд растёт $$$n$$$ пальм, обозначим их высоты $$$a_i$$$. Во время прогулки Пенчик заметил пустынного кролика, который готовится прыгнуть вдоль линии пальм.

Кролик может перепрыгнуть с $$$i$$$-го дерева на $$$j$$$-е, если верно ровно одно из следующих условий:

  • $$$j < i$$$ и $$$a_j > a_i$$$: кролик может прыгнуть назад на более высокое дерево.
  • $$$j > i$$$ и $$$a_j < a_i$$$: кролик может прыгнуть вперёд на более низкое дерево.

Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ определите максимальную высоту среди всех деревьев, которые может достичь кролик, если он начнёт с $$$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$$$.

Пример
Входные данные
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
Выходные данные
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$$$.