G. Удаление перестановки
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана перестановка $$$p$$$ длины $$$n$$$.

Вы можете выполнять операции двух типов:

  • отметить все такие позиции $$$i$$$, что $$$1 \le i < n$$$ и $$$p_i < p_{i + 1}$$$, и одновременно удалить элементы на этих позициях;
  • отметить все такие позиции $$$i$$$, что $$$2 \le i \le n$$$ и $$$p_{i - 1} > p_i$$$, и одновременно удалить элементы на этих позициях.

Ваша задача — для каждого целого числа от $$$1$$$ до $$$(n-1)$$$ посчитать минимальное количество вышеописанных операций, чтобы удалить это число из перестановки.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$2 \le n \le 250\,000$$$).

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$). Массив $$$p$$$ является перестановкой.

Дополнительные ограничения на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.

Выходные данные

Для каждого набора выведите $$$(n-1)$$$ целых чисел, $$$i$$$-е из которых — минимальное количество вышеописанных операций, чтобы удалить число $$$i$$$ из перестановки.

Пример
Входные данные
5
4
4 2 1 3
2
1 2
6
5 4 1 3 2 6
7
5 6 1 3 7 2 4
5
3 1 2 5 4
Выходные данные
1 1 2
1
1 1 2 1 3
1 1 1 2 1 2
1 1 2 1