Олимпиадный тренинг

Задача . D. Восстановление перестановки


У Монокарпа была перестановка \(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\) по всем наборам входных данных не превосходит \(5 \cdot 10^5\);
  • существует хотя бы одна перестановка \(a\), по которой описанным в условии процессом можно получить заданный массив \(b\).
Выходные данные

Для каждого набора входных данных выведите \(n\) целых чисел — перестановку \(a\), которая соответствует заданному массиву \(b\). Если таких перестановок несколько — выведите любую.


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

time 4000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w644
Комментарий учителя