CF1713C Build Permutation

一个大小为 $n$ 的 $0$ 下标数组 $a$ 被称为“好”的，如果对于所有合法的下标 $i$（$0 \le i \le n-1$），都有 $a_i + i$ 是一个完全平方数$^\dagger$。 给定一个整数 $n$。请你找到一个 $[0,1,2,\ldots,n-1]$ 的排列$^\ddagger$ $p$，使其是“好”的，或者判断不存在这样的排列。 $^\dagger$ 如果存在一个整数 $y$ 使得 $x = y^2$，则整数 $x$ 被称为完全平方数。 $^\ddagger$ 如果数组 $b$ 由数组 $a$ 的元素任意排列得到，则 $b$ 是 $a$ 的一个排列。例如，$[4,2,3,4]$ 是 $[3,2,4,4]$ 的一个排列，而 $[1,2,2]$ 不是 $[1,2,3]$ 的排列。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例仅一行，包含一个整数 $n$（$1 \le n \le 10^5$），表示排列 $p$ 的长度。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，如果存在答案，输出 $n$ 个互不相同的整数 $p_0, p_1, \dots, p_{n-1}$（$0 \le p_i \le n-1$），表示排列 $p$；如果不存在答案，输出 $-1$。

在第一个测试用例中，$n=3$。数组 $p = [1, 0, 2]$ 是“好”的，因为 $1 + 0 = 1^2$，$0 + 1 = 1^2$，$2 + 2 = 2^2$。 在第二个测试用例中，$n=4$。数组 $p = [0, 3, 2, 1]$ 是“好”的，因为 $0 + 0 = 0^2$，$3 + 1 = 2^2$，$2+2 = 2^2$，$1+3 = 2^2$。 由 ChatGPT 4.1 翻译