P16534 [THUPC 2026 决赛] 年鉴整理

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）决赛。 题解等资源可在 https://github.com/dapingguo8/THUPC2026-final 查看。 > 茶话会临近尾声，作为庆典十周年专属的怀旧环节，小 T 特意找出了历届 THUPC 的珍贵档案---一排记录了十年点滴的赛事年鉴，供大家传阅。 > > 翻阅过后，两人准备将年鉴放回书架。由于岁月流逝，年鉴的破损程度参差不齐。心思细腻的小 S 提议，在放回时将它们按破损程度严格递增重新排序，以此直观地展现时间沉淀的痕迹。然而，年鉴的纸张已经十分脆弱，每次只能极其小心地将其中的一本向前平移一位，且这无可避免地会略微增加该年鉴的破损度。更棘手的是，留给他们的整理时间十分有限。小 S 想知道，能否在有限的操作次数内，将这些年鉴放回书架并整理得井然有序呢？

书架上摆放着 $n$ 本年鉴。初始时，第 $i \ (1 \le i \le n)$ 本年鉴的破损度为 $a_i$。 每次移动时，首先需要选择一个位置 $p \ (1 \le p \le n - 1)$，然后将第 $p + 1$ 本年鉴向前移动至第 $p$ 本年鉴前，移动后它的破损度将会增加 $1$。 由于时间有限，总共只能进行不超过 $n ^ 2 - n$ 次移动。作为众多翻阅年鉴的参与者之一，你需要帮助小 S 规划出一组具体的移动方案，使得最终书架上的年鉴破损度从左到右**严格递增**。

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $T \ (1 \le T \le 10)$，表示数据组数。对于每组测试数据： - 第一行包含一个正整数 $n \ (1 \le n \le 500)$，表示年鉴的数量。 - 第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n \ (1 \le a_i \le 10^9)$，分别表示初始时每一本年鉴的破损度

对于每组测试数据，若存在可行的移动方案： - 第一行输出一个非负整数 $k \ (0 \le k \le n ^ 2 - n)$，表示移动次数。 - 第二行输出 $k$ 个正整数 $p_1, p_2, \dots, p_k \ (1 \le p_i \le n - 1)$，分别表示每次移动选定的位置。 若无法使得最终书架上的年鉴破损度从左到右严格递增，则仅输出一行一个整数 $-1$。

- 对于第一组测试数据，序列 $[1,2]$ 已为严格增序列。 - 对于第二组测试数据，无法在规定步数内将序列 $[2,1]$ 变为严格增序列。 - 对于第三组测试数据，首先选择下标 $2$，将序列变为 $[4,2,5]$；随后选择下标 $1$，将序列变为 $[3,4,5]$。