CF2273A Lavencia Oranges

René 在经历两年寒冷的 Lavencia 生活后，即将离开，手头有 $n$ 个 Lavencia 橙子和 $n$ 个空袋子（编号从 $1$ 到 $n$），每个橙子和袋子也都编号 $1$ 到 $n$。René 按照数组 $a$ 装橙子：第 $i$ 个橙子放入编号为 $a_i$ 的袋子。 Lavencia 对出口有严格的检验流程，由 Jacqueline 执行：她选择一个整数 $s$，并没收所有恰好装有 $s$ 个橙子的袋子，取使 René 被没收橙子数最多的 $s$。数组 $a$ 的代价定义为 Jacqueline 可以没收的最大橙子数。 更正式地，给定数组 $a$，令 $c_i$ 表示在 $a$ 中恰好出现 $i$ 次的元素个数。则 $a$ 的代价为： $$ \max_{0 \le i \le n} i \cdot c_i $$ 给定 $n$，请构造一个数组 $a$，使得代价最小。

每个测试点包含若干测试用例。第一行包含测试用例个数 $t$（$1 \le t \le 10^4$）。接下来 $t$ 行每行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对每个测试用例输出两行。 第一行输出一个整数——最小可能代价。 第二行输出 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le n$）——任意一个能实现最小代价的方案。

在第一个测试用例中，René 分别向四个袋子中放了 $1$、$1$、$2$、$0$ 个橙子。当 Jacqueline 选择 $1$ 时，她没收了袋子 $1$ 和 $2$，René 损失 $2$ 个橙子。选择 $2$ 时，没收了袋子 $3$，也是 $2$ 个橙子。因此代价为 $2$。可以证明这是该情况下的最小代价。 在第二个测试用例中，袋子 $1$ 中有 $2$ 个橙子、袋子 $2$ 有 $3$ 个、其它袋子为空。选择 $2$ 时，René 损失 $2$ 个橙子，选择 $3$ 时损失 $3$ 个橙子，因此代价为 $3$。也可以证明在这个情况下 $3$ 是最小代价。 由 ChatGPT 5 翻译