CF2246F Whoname and Unsorted Array

给定一个长度为 $n$ 的排列 $p$，你可以对其执行如下操作若干次（可以是零次）： - 选择一个下标 $i$，其中 $1 \leq i \leq n-1$，将 $p_i$ 移动到 $p_1$ 的位置（将其间的所有元素依次向右移动），并将 $p_{i+1}$ 移动到 $p_n$ 的位置（将其间的所有元素依次向左移动）。形式化地说，你可以将 $p=[p_1, \ldots, p_n]$ 变换为 $p'=[p_i, p_1, p_2, \ldots, p_{i-1}, p_{i+2}, p_{i+3}, \ldots, p_n, p_{i+1}]$。 请给出一个不超过 $4n$ 次操作的合理操作序列，使得对于所有 $i\,(1\le i\le n)$ 都有 $p_i=i$，如果不存在合理的操作序列则输出 $-1$。 可以证明，如果存在合理的操作序列，则存在长度不超过 $4n$ 的合理序列。 $^*$ 长度为 $n$ 的排列，是指由 $1$ 到 $n$ 的 $n$ 个互不相同的整数任意排列组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但数组中出现了 $4$）。

每个测试点包含多个测试用例。第一行包含测试用例个数 $t$（$1\le t\le 10^3$）。每组测试用例描述如下。 第一行包含一个整数 $n$（$2 \leq n \leq 5000$），表示排列的长度。 第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n\ (1 \leq p_i \leq n)$。 保证 $p$ 是一个排列。 保证所有测试用例的 $n$ 之和不超过 $5000$。

如果不存在合理的操作序列，输出 $-1$。 否则，第一行输出 $x\ (0\le x\le 4n)$，表示排序所需的操作数。第二行输出 $x$ 个整数 $i_1, \ldots, i_x$，其中 $i_j\ (1\leq i_j\leq n-1)$ 表示第 $j$ 次操作所选的下标。

对于第一个样例，可以证明不存在任何操作序列能够将排列排序。 对于第二个样例，一个合理的操作序列是 $[3, 2, 1] \xrightarrow{i_1=1} [3, 1, 2] \xrightarrow{i_2=2} [1, 3, 2] \xrightarrow{i_3=1} [1, 2, 3]$。 对于第三个样例，一个合理的操作序列是 $[1, 5, 4, 3, 2] \xrightarrow{i_1=2} [5, 1, 3, 2, 4] \xrightarrow{i_2=2} [1, 5, 2, 4, 3] \xrightarrow{i_3=3} [2, 1, 5, 3, 4] \xrightarrow{i_4=2} [1, 2, 3, 4, 5]$。 对于第四个样例，一个合理的操作序列是 $[4, 3, 2, 1] \xrightarrow{i_1=1} [4, 2, 1, 3] \xrightarrow{i_2=3} [1, 4, 2, 3] \xrightarrow{i_3=1} [1, 2, 3, 4]$。 由 ChatGPT 5 翻译