{"problem":{"name":"Swap to Sort","description":{"content":"You are given a permutation $P=(P_1,P_2,\\ldots,P_N)$ of $(1,2,\\ldots,N)$. You can repeat the following two kinds of operations in any order to make $P$ sorted in increasing order. *   Operation $A$: ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc147_b"},"statements":[{"statement_type":"Markdown","content":"You are given a permutation $P=(P_1,P_2,\\ldots,P_N)$ of $(1,2,\\ldots,N)$.\nYou can repeat the following two kinds of operations in any order to make $P$ sorted in increasing order.\n\n*   Operation $A$: Choose an integer $i$ such that $1 \\leq i \\leq N-1$, and swap $P_i$ and $P_{i+1}$.\n    \n*   Operation $B$: Choose an integer $i$ such that $1 \\leq i \\leq N-2$, and swap $P_i$ and $P_{i+2}$.\n    \n\nFind a sequence of operations with the following property:\n\n*   The number of Operations $A$ is the minimum possible.\n    \n*   The total number of operations is not larger than $10^5$.\n    \n\nUnder the Constraints of this problem, we can prove that a solution always exists.\n\n## Constraints\n\n*   $2 \\leq N \\leq 400$\n*   $1 \\leq P_i \\leq N \\,(1 \\leq i \\leq N)$\n*   $P_i \\neq P_j \\,(1 \\leq i < j \\leq N)$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$P_1$ $P_2$ $\\ldots$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc147_b","tags":[],"sample_group":[["4\n3 2 4 1","4\nA 3\nB 1\nB 2\nB 2\n\nIn this Sample Output, $P$ changes like this: $(3,2,4,1) \\rightarrow (3,2,1,4) \\rightarrow (1,2,3,4) \\rightarrow (1,4,3,2) \\rightarrow (1,2,3,4)$.\nNote that you don't have to minimize the total number of operations."],["3\n1 2 3","0"],["6\n2 1 4 3 6 5","3\nA 1\nA 3\nA 5"]],"created_at":"2026-03-03 11:01:13"}}