問題文

$Q$ 個のクエリが与えられます。各クエリでは $6$ 以上の偶数 $N$ と $\left(1,2,\cdots,N\right)$ の順列 $P=(P_0,P_1,\cdots,P_{N-1})$ (添え字が $0$ から始まることに注意してください)が与えられるので、 $0$ 以上 $N-1$ 以下の整数 $i$ を1つ出力してください。

あなたの提出したプログラムを用いて、ジャッジは以下のゲームを行います。このゲームが成功したとき、またそのときに限り、そのテストケースはACと判定されます。

最初にジャッジはあなたのプログラムを $2$ つの独立したプロセスとして実行します。便宜上、これらをプロセス $1$ 、プロセス $2$ と呼んで区別します。 ただし、それぞれのプロセスには自身がプロセス $1$ として実行されているのかプロセス $2$ として実行されているのかの情報は与えられません。 まずジャッジはクエリ数 $Q$ を決定し、$2$ つのプロセスそれぞれに $Q$ を入力します。その後、以下の操作を $Q$ 回繰り返します。 (下のサンプルケースの説明も参考にしてください。)

1. $6$ 以上の偶数 $N$ と $\left(1,2,\cdots,N\right)$ の順列 $P=(P_0,P_1,\cdots,P_{N-1})$ 、および $0$ 以上 $N-1$ 以下の整数 $r$ と $p\in \{1,2\}$ なる整数 $p$ を決定する。なお、このうち $r$ および $p$ は各プロセスには与えられず、ジャッジのみが持つ非公開情報である。
2. プロセス $p$ に $N$ と $P$ を入力し、出力を受け取る。受け取った整数を $i$ とする。
3. $P_i$ から始まる長さ $\frac{N}{2}$ の区間を円環状に取り、その部分を反転させる。そして、この操作の対象となった値の集合を $X$ と定める。 より厳密には、この時点での $P$ の値について、整数の集合 $X$ を $X=\{P_{(i+j) \bmod N}|0 \leq j < \frac{N}{2}\}$ と定め、その後 $0 \leq j < \frac{N}{2}$ なる各整数 $j$ について、 $P_{(i+j) \bmod N}$ を $P_{(i+\frac{N}{2}-1-j) \bmod N}$ で同時に置き換える。
4. $P$ を $r$ 回だけ左に巡回シフトする。 (すなわち $0 \leq j < N$ なる各整数 $j$ について $P_j$ を $P_{(j+r) \bmod N}$ で同時に置き換える。)
5. $N$ と $P$ をプロセス $p$ ではない方のプロセス(すなわちプロセス $3-p$ )に入力し、出力を受け取る。受け取った整数を $i'$ とする。
6. この時点での $P$ の値について、整数の集合 $Y$ を $Y=\{P_{(i'+j) \bmod N}|0\le j < \frac{N}{2} \}$ と定める。このとき、 $X$ と $Y$ の共通部分が空であれば操作は成功とし、そうでなければ失敗とする。

$Q$ 回の操作の全てで成功した場合、またその場合のみ、ゲームは成功となります。

制約

• $1 \le Q \le 10000$
• $6 \le N \le 2 \times 10^5$
• $N$ は偶数
• $(P_0,P_1,\cdots ,P_{N-1})$ は $(1,2,\cdots ,N)$ の順列
• $Q$ 個のクエリにわたる $N$ の総和は $2 \times 10^5$ 以下
• 入力は全て整数

入出力

最初にクエリ数 $Q$ が次の形式で入力されます。

$Q$

その後、各クエリが次の形式で入力されます。

$N$
$P_0\ P_1\ \cdots\ P_{N-1}$

各クエリに対して、以下の形式で出力してください。

$i$

なお、両プロセスともが $1$ つのクエリを処理し終えるまで、次のクエリは入力されないので注意してください。

出力が制約を満たさない場合や、問題文中の操作に失敗した場合、次のクエリは与えられず、代わりに-1が入力されます。この場合はただちにプログラムを終了してください。

注意点

• 出力のたびに末尾に改行を入れ、必ず標準出力をflushしてください。
• 不正な出力をした場合や途中でプログラムが終了した場合などのジャッジ結果は不定です。

サンプル

例として、 $Q=1$ のケースを考えます。まず両プロセスには次のような入力が与えられます。

1

ジャッジが $N=8,r=3,p=1,P=(4,1,6,8,2,3,7,5)$ と決定したとします。 このとき、プロセス $p=1$ には次のような入力が与えられます。

8
4 1 6 8 2 3 7 5

これに対してプロセス $1$ が次のように出力したとします。

6

このとき、 $X=\{7,5,4,1\}$ です。 $P$に区間反転操作を施すと $P=(5,7,6,8,2,3,1,4)$ となり、さらに $r=3$ 回左に巡回シフトを行うので、プロセス $p$ ではない方、すなわちプロセス $2$ には次のような入力が与えられます。

8
8 2 3 1 4 5 7 6

これに対してプロセス $2$ が次のように出力したとします。

7

このとき $Y=\{6,8,2,3\}$ です。 $X\cap Y= \emptyset$ なので、この操作は成功となります。

$Q=1$ 回の操作が全て成功したので、このケースはACと判定されます。