У Монокарпа была перестановка $$$a$$$ состоящая из $$$n$$$ чисел $$$1$$$, $$$2$$$, ..., $$$n$$$ (перестановка — это массив, в котором каждый элемент от $$$1$$$ до $$$n$$$ встречается ровно один раз).
Монокарп составил массив целых чисел $$$b$$$ размера $$$n$$$, где $$$b_i = \left\lfloor \frac{i}{a_i} \right\rfloor$$$. Например, если перестановка $$$a$$$ равна $$$[2, 1, 4, 3]$$$, то массив $$$b$$$ равен $$$\left[ \left\lfloor \frac{1}{2} \right\rfloor, \left\lfloor \frac{2}{1} \right\rfloor, \left\lfloor \frac{3}{4} \right\rfloor, \left\lfloor \frac{4}{3} \right\rfloor \right] = [0, 2, 0, 1]$$$.
К сожалению, Монокарп потерял свою перестановку, поэтому он хочет восстановить ее. Ваша задача — найти перестановку $$$a$$$, которая соответствует заданному массиву $$$b$$$. Если таких перестановок несколько — выведите любую. Гарантируется, что хотя бы одна подходящая перестановка существует.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных.
Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$).
Вторая строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i \le n$$$).
Дополнительные ограничения на входные данные:
Для каждого набора входных данных выведите $$$n$$$ целых чисел — перестановку $$$a$$$, которая соответствует заданному массиву $$$b$$$. Если таких перестановок несколько — выведите любую.
440 2 0 121 150 0 1 4 130 1 3
2 1 4 3 1 2 3 4 2 1 5 3 2 1
Название |
---|