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

Элемент $$$b_i$$$ ($$$1\le i\le m$$$) в массиве $$$b_1, b_2, \ldots, b_m$$$ является локальным минимумом, если выполняется хотя бы одно из следующих условий:

  • $$$2\le i\le m - 1$$$ и $$$b_i \lt b_{i - 1}$$$ и $$$b_i \lt b_{i + 1}$$$, или
  • $$$i = 1$$$ и $$$b_1 \lt b_2$$$, или
  • $$$i = m$$$ и $$$b_m \lt b_{m - 1}$$$.

Аналогично, элемент $$$b_i$$$ ($$$1\le i\le m$$$) в массиве $$$b_1, b_2, \ldots, b_m$$$ является локальным максимумом, если выполняется хотя бы одно из следующих условий:

  • $$$2\le i\le m - 1$$$ и $$$b_i \gt b_{i - 1}$$$ и $$$b_i \gt b_{i + 1}$$$, или
  • $$$i = 1$$$ и $$$b_1 \gt b_2$$$, или
  • $$$i = m$$$ и $$$b_m \gt b_{m - 1}$$$.

Обратите внимание, что локальные минимумы и максимумы не определены для массивов, состоящих только из одного элемента.

Существует скрытая перестановка$$$^{\text{∗}}$$$ $$$p$$$ длины $$$n$$$. К перестановке $$$p$$$ последовательно применяются следующие две операции, начиная с операции 1, до тех пор, пока в $$$p$$$ не останется только один элемент:

  • Операция 1 — удалить все элементы $$$p$$$, которые не являются локальными минимумами.
  • Операция 2 — удалить все элементы $$$p$$$, которые не являются локальными максимумами.

Более конкретно, операция 1 применяется на каждой нечетной итерации, а операция 2 применяется на каждой четной итерации, пока в $$$p$$$ не останется только один элемент.

Для каждого индекса $$$i$$$ ($$$1\le i\le n$$$) пусть $$$a_i$$$ будет номером итерации, на которой элемент $$$p_i$$$ был удален, или $$$-1$$$, если он никогда не был удален.

Можно доказать, что в $$$p$$$ останется только один элемент после не более чем $$$\lceil \log_2 n\rceil$$$ итераций (другими словами, $$$a_i \le \lceil \log_2 n\rceil$$$).

Вам дан массив $$$a_1, a_2, \ldots, a_n$$$. Ваша задача состоит в том, чтобы построить любую перестановку $$$p$$$ из $$$n$$$ элементов, которая удовлетворяет массиву $$$a$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество элементов в перестановке $$$p$$$.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le \lceil\log_2 n\rceil$$$ или $$$a_i = -1$$$) — номер итерации, на которой элемент $$$p_i$$$ был удален.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Гарантируется, что существует по крайней мере одна перестановка $$$p$$$, которая удовлетворяет массиву $$$a$$$.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел, представляющих элементы перестановки, удовлетворяющей массиву $$$a$$$.

Если существует несколько решений, вы можете вывести любое из них.

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

В первом наборе входных данных операции будут применены к перестановке $$$[3, 2, 1]$$$ следующим образом:

  1. Единственный локальный минимум в $$$[3, 2, 1]$$$ это $$$1$$$. Следовательно, элементы $$$3$$$ и $$$2$$$ удаляются. Остается только один элемент; процесс завершается.

Это удовлетворяет массиву $$$a = [1, 1, -1]$$$, так как оба $$$p_1$$$ и $$$p_2$$$ были удалены на итерации номер $$$1$$$, в то время как $$$p_3$$$ не был удален.

Во втором наборе входных данных операции будут применены к перестановке $$$p = [4, 3, 5, 1, 2]$$$ следующим образом:

  1. Локальные минимумы в $$$[4, 3, 5, 1, 2]$$$ это $$$3$$$ и $$$1$$$. Следовательно, элементы $$$4$$$, $$$5$$$ и $$$2$$$ удаляются.
  2. Единственный локальный максимум в $$$[3, 1]$$$ это $$$3$$$. Следовательно, элемент $$$1$$$ удаляется. Остается только один элемент; процесс завершается.

Это удовлетворяет массиву $$$a = [1, -1, 1, 2, 1]$$$, так как элементы $$$p_1 = 4$$$, $$$p_3 = 5$$$ и $$$p_5 = 2$$$ были удалены на итерации $$$1$$$, элемент $$$p_4 = 1$$$ был удален на итерации $$$2$$$, а элемент $$$p_2 = 3$$$ не был удален.

В третьем наборе входных данных операции будут применены к перестановке $$$[6, 7, 2, 4, 3, 8, 5, 1]$$$ следующим образом:

  1. Локальные минимумы в $$$[6, 7, 2, 4, 3, 8, 5, 1]$$$ это $$$6$$$, $$$2$$$, $$$3$$$ и $$$1$$$. Следовательно, элементы $$$7$$$, $$$4$$$, $$$8$$$ и $$$5$$$ удаляются.
  2. Локальные максимумы в $$$[6, 2, 3, 1]$$$ это $$$6$$$ и $$$3$$$. Следовательно, элементы $$$2$$$ и $$$1$$$ удаляются.
  3. Единственный локальный минимум в $$$[6, 3]$$$ это $$$3$$$. Следовательно, элемент $$$6$$$ удаляется. Остается только один элемент; процесс завершается.

В четвертом наборе входных данных одна из перестановок, удовлетворяющих ограничениям, это [$$$6$$$, $$$5$$$, $$$2$$$, $$$1$$$, $$$3$$$, $$$4$$$, $$$7$$$]. $$$1$$$ является единственным локальным минимумом, поэтому только он останется после первой итерации. Обратите внимание, что существуют и другие допустимые перестановки; например, [$$$6$$$, $$$4$$$, $$$3$$$, $$$1$$$, $$$2$$$, $$$5$$$, $$$7$$$] также будет считаться правильной.