{"problem":{"name":"Odd Even Sort","description":{"content":"Given is a sequence $p$ which is a permutation of $(1,2, \\ldots, N)$. Initially, the $n$\\-th term of $p$ is $p_{n}$. Your objective is to sort $p$ in ascending order in at most $N^2$ _operations_. In ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc121_c"},"statements":[{"statement_type":"Markdown","content":"Given is a sequence $p$ which is a permutation of $(1,2, \\ldots, N)$. Initially, the $n$\\-th term of $p$ is $p_{n}$.\nYour objective is to sort $p$ in ascending order in at most $N^2$ _operations_. In one operation, you make the following change on $p$:\n\n*   In the $1$\\-st, $3$\\-rd, and subsequent **odd-numbered** operations, you choose an **odd number** $n$ between $1$ and $N-1$ (inclusive) to swap $p_n$ and $p_{n+1}$.\n*   In the $2$\\-nd, $4$\\-th, and subsequent **even-numbered** operations, you choose an **even number** $n$ between $2$ and $N-1$ (inclusive) to swap $p_n$ and $p_{n+1}$.\n\nWe can prove that the objective is always achievable under the Constraints of this problem. Find one sequence of operations that achieves the objective.\nYou will be given $T$ test cases and asked to solve each of them.\n\n## Constraints\n\n*   All values in input are integers.\n*   $1 \\leq T \\leq 250$\n*   $2 \\leq N \\leq 500$\n*   $1 \\leq p_i \\leq N$\n*   $p$ is a permutation of $(1,2,\\ldots,N)$.\n*   In one input file, the sum of $N$ does not exceed $500$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_{1}$\n$\\vdots$\n$\\mathrm{case}_{T}$\n\nEach case is in the following format:\n\n$N$\n$p_1$ $\\cdots$ $p_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc121_c","tags":[],"sample_group":[["2\n5\n2 1 3 5 4\n2\n1 2","2\n1 4\n0\n\n*   Here is the description for the $1$\\-st test case.\n    *   Choosing $1$ in the $1$\\-st operation makes $p = (1,2,3,5,4)$.\n    *   Choosing $4$ in the $2$\\-nd operation makes $p = (1,2,3,4,5)$.\n    *   Note that although $(1,4)$ is a valid sequence of operations, $(4, 1)$ is not.\n*   Also note that it is allowed to perform no operation, and it is not required to minimize the number of operations."]],"created_at":"2026-03-03 11:01:14"}}