题目描述

$(1,2,\ \ldots,\ N)$ を並び替えた数列 $p$ が与えられます。 はじめ、$p$ の第 $n$ 項は $p_{n}$ です。

あなたの目的は $N^2$ 回以下 操作 を行い $p$ を昇順に並び替えることです。 あなたは操作により以下のように $p$ を変更することができます。

• 奇数 回目の操作では $1$ 以上 $N-1$ 以下の 奇数 $n$ を選んで $p_n$ と $p_{n+1}$ を入れ替えます。
• 偶数 回目の操作では $2$ 以上 $N-1$ 以下の 偶数 $n$ を選んで $p_n$ と $p_{n+1}$ を入れ替えます。

この問題の制約下で必ず目的を達成できることが証明できます。 そのような操作列を $1$ つ求めてください。

$T$ 個のテストケースが与えられるのでそれぞれについて答えを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$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$ 回目の操作で選んだ整数を表す。

全てのテストケースにおいて目的が達成される操作列が出力されたならば正解となる。

题目大意

给出一个长度为 $n$ 的排列 $p$。

你可以进行最多 $n^2$ 次操作，对于第 $i$ 次操作：

• $i$ 为奇数，则你必须选择一个奇数位置 $q$，交换 $p_q$ 和 $p_{q + 1}$。
• $i$ 为偶数，则你必须选择一个偶数位置 $q$，交换 $p_q$ 和 $p_{q + 1}$。

询问你将排列变为升序的方案。如果有多种方案任意输出一种即可。

本题共有 $T$ 组数据。

——by hswfwkj

2
5
2 1 3 5 4
2
1 2

2
1 4
0

提示

制約

• 与えられる入力は全て整数
• $1\ \leq\ T\ \leq\ 250$
• $2\ \leq\ N\ \leq\ 500$
• $1\ \leq\ p_i\ \leq\ N$
• $p$ は $(1,2,\ldots,N)$ を並び替えて得られる。
• $1$ つの入力ファイルにおいて $N$ の総和は $500$ を超えない。

Sample Explanation 1

- $1$ つ目のテストケースについて説明します。 - $1$ 回目の操作で $1$ を選ぶと $p$ は $(1,2,3,5,4)$ となります。 - $2$ 回目の操作で $4$ を選ぶと $p$ は $(1,2,3,4,5)$ となります。 - $(1,4)$ は操作列として正しいですが、$(4,1)$ は操作列として正しくないことに注意してください。 - 操作を $1$ 度も行わなくともよいこと、操作回数を最小にする必要はないことに注意してください。