← 返回题目列表

Codeforces · 1701/D

D. 排列恢复

中文机器翻译题面 查看原题

Monocarp 具有 $$$n$$$ 整数 $$$1$$$、$$$2$$$、...、$$$n$$$ 的排列 $$$a$$$(排列是一个数组,其中从 $$$1$$$ 到 $$$n$$$ 的每个元素恰好出现一次)。

然后 Monocarp 计算了一个大小为 $$$n$$$ 的整数数组 $$$b$$$,其中 $$$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]$$$。

不幸的是,Monocarp 失去了他的排列,所以他想恢复它。您的任务是找到与给定数组 $$$b$$$ 对应的排列 $$$a$$$。如果有多种可能的排列,则打印其中任何一个。测试的构造方式使得至少存在一种合适的排列。

输入

第一行包含一个整数 $$$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$$$ 整数 - 对应于给定数组 $$$b$$$ 的排列 $$$a$$$。如果有多种可能的排列,则打印其中任何一个。

示例

输入 #1

4
4
0 2 0 1
2
1 1
5
0 0 1 4 1
3
0 1 3

输出 #1

2 1 4 3 
1 2 
3 4 2 1 5 
3 2 1