CF2137D Replace with Occurrences

题目描述

给定一个长度为 $n$ 的序列 $b$,要求构造出另一个长度为 $n$ 的序列 $a$,使得对于新序列中每个元素 $a_i$,满足 $a_i$ 在 $a$ 中的出现次数恰好为 $b_i$。要求 $1 \le a_i \le n$。

输入格式

**本题有多组测试数据。** 第一行一个正整数 $T (1 \le T \le 10^4)$ 表示测试数据数量。 随后 $2T$ 行,第 $i + 1$ 至 $i + 2$ 行为第 $i$ 组测试数据。第 $i + 1$ 行一个整数 $n (1 \le n \le 2 \cdot 10 ^ 5)$,表示 $b$ 的长度,第二行 $n$ 个整数 $b_i (1 \le b_i \le n)$,表示 $b$ 序列。

输出格式

输出答案。若有多个答案,输出任意一个均可。如果不存在答案,输出 `-1`。

说明/提示

在第一组测试数据中,没有一个数组 $a$ 符合要求。 在第二组测试数据中, $4, 5, 6$ 分别出现了 $1, 2, 3$ 次,所以 $a = \{ 4, 5, 5, 6, 6, 6 \}$ 符合要求。