分数: 500 点
问题陈述
给定的是一个序列 p 这是一个排列 (1,2, \ldots, N)。 最初, n第 学期 p is p_{n}.
你的目标是排序 p 最多按升序排列 N^2 操作。 在一项操作中,您可以对 p:
- 在 1-st, 3-rd 及后续 奇数 操作,您选择一个 奇数 n 之间 1 和 N-1 (含)进行交换 p_n 和 p_{n+1}.
- 在 2-nd, 4-th 及后续 偶数 操作,您选择一个 偶数 n 之间 2 和 N-1 (含)进行交换 p_n 和 p_{n+1}.
我们可以证明,在这个问题的约束下,目标总是可以实现的。 找到实现目标的一系列操作。
你将得到 T 测试用例并要求解决每个用例。
约束
- 输入中的所有值都是整数。
- 1 \leq T \leq 250
- 2 \leq N \leq 500
- 1 \leq p_i \leq N
- p 是一个排列 (1,2,\ldots,N).
- 在一个输入文件中, N 不超过 500.
输入
输入由标准输入按以下格式给出:
T
\mathrm{case}_{1}
\vdots
\mathrm{case}_{T}
每个案例的格式如下:
N p_1 \cdots p_N
输出
对于每个 T 测试用例,按照给出的顺序,按以下格式打印您的答案:
M a_1 \cdots a_M
在这里, M 代表操作序列的长度,并且 a_i 代表您在中选择的整数 i-第次操作。
如果对于每个测试用例,您的操作序列都实现了目标,则您的输出将被视为正确。
示例输入 1
2 5 2 1 3 5 4 2 1 2
示例输出 1
2 1 4 0
- 这是对 1-st 测试用例。
- 选择 1 在 1-st 操作使得 p = (1,2,3,5,4).
- 选择 4 在 2-nd 操作使得 p = (1,2,3,4,5).
- 请注意,虽然 (1,4) 是有效的操作序列, (4, 1) 不是。
- 还要注意的是,允许不执行任何操作,并且不要求最小化操作次数。