CF2246F.Whoname and Unsorted Array

Given a permutation$^{\text{∗}}$ $p$ of length $n$, you may perform the following operation on it any number of times (possibly zero):

• Choose an index $i$ where $1 \leq i \leq n-1$, and move $p_i$ to $p_1$ (shifting everything in between to the right) and $p_{i+1}$ to $p_n$ (shifting everything in between to the left). Formally, you may transform $p = [p_1, \ldots, p_n]$ into $p' = [p_i, p_1, p_2, \ldots, p_{i-1}, p_{i+2}, p_{i+3}, \ldots, p_n, p_{i+1}].$

Provide a valid sequence of operations of length at most $4n$ to make $p_i = i$ for all $i\,(1 \le i \le n)$, or print $-1$ if no sequence exists.

It can be shown that if a valid sequence of operations exists, there is a valid sequence of length at most $4n$ operations.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

给定一个长度为 $n$ 的排列$^{\text{∗}}$ $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$ 的合法操作序列。

$^{\text{∗}}$长度为 $n$ 的排列是指由 $1$ 到 $n$ 中互不相同的 $n$ 个整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是排列（数字 $2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line contains an integer $n\,(2 \leq n \leq 5000)$ — the length of the permutation.

The second line contains $n$ integers $p_1, p_2, \ldots, p_n \, (1 \le p_i \le n)$.

It is guaranteed that $p$ is a permutation.

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^3$）。随后是各测试用例的描述。

第一行包含一个整数 $n$（$2 \leq n \leq 5000$）—— 排列的长度。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1 \le p_i \le n$）。

保证 $p$ 是一个排列。

保证所有测试用例的 $n$ 之和不超过 $5000$。

If there does not exist a valid sequence of operations, output $-1$.

Otherwise, on the first line, output $x\,(0 \leq x \leq 4n)$, the number of operations needed to sort the permutation. On the second line, output $x$ integers $i_1, \ldots, i_x$ where $i_j$ ($1 \leq i_j \leq n-1$) denotes the index corresponding to the $j$-th operation.

如果不存在合法的操作序列，则输出 $-1$。

否则，第一行输出 $x\,(0 \leq x \leq 4n)$，表示将排列排序所需的操作次数；第二行输出 $x$ 个整数 $i_1, \ldots, i_x$，其中每个 $i_j$（$1 \leq i_j \leq n-1$）表示第 $j$ 次操作所对应的下标。

For the first example, it can be shown that no sequence of operations can sort the permutation.

For the second example, one valid sequence of operations is $ [3, 2, 1] \xrightarrow{i_1=1} [3, 1, 2] \xrightarrow{i_2=2} [1, 3, 2] \xrightarrow{i_3=1} [1, 2, 3]. $

For the third example, one valid sequence of operations is $ [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] $

For the fourth example, one valid sequence of operations is $ [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] $

对于第一个例子，可以证明不存在任何操作序列能够将该排列排序。

对于第二个例子，一个有效的操作序列是 $ [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] $