{"problem":{"name":"Insertion Sort 2","description":{"content":"A permutation $P=(P_1,P_2,\\ldots,P_N)$ of $(1,2,\\ldots,N)$ is given. Determine whether it is possible to rearrange $P$ in ascending order by performing the following operation at most $2\\times 10^3$ t","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc162_b"},"statements":[{"statement_type":"Markdown","content":"A permutation $P=(P_1,P_2,\\ldots,P_N)$ of $(1,2,\\ldots,N)$ is given.\nDetermine whether it is possible to rearrange $P$ in ascending order by performing the following operation at most $2\\times 10^3$ times, and if possible, show one such sequence of operations.\n\n*   Choose integers $i$ and $j$ such that $1\\leq i \\leq N-1,0 \\leq j \\leq N-2$. Let $Q = (Q_1, Q_2,\\ldots,Q_{N-2})$ be the sequence obtained by removing $(P_i,P_{i+1})$ from $P$. Replace $P$ with $(Q_1,\\ldots,Q_j, P_i, P_{i+1}, Q_{j+1},\\ldots,Q_{N-2})$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^3$\n*   $P$ is a permutation of $(1,2,\\ldots,N)$.\n*   All input values are integers.\n\n## Input\n\nThe input 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":"arc162_b","tags":[],"sample_group":[["5\n1 4 2 3 5","Yes\n1\n3 1\n\nPerform the operation with $i=3,j=1$.\nThen, $Q=(P_1,P_2,P_5)=(1,4,5)$, so you get $P=(Q_1,P_3,P_4,Q_2,Q_3) = (1,2,3,4,5)$.\nThus, $P$ can be rearranged in ascending order with one operation."],["2\n2 1","No\n\nIt can be proved that $P$ cannot be rearranged in ascending order within $2\\times 10^3$ operations."],["4\n3 4 1 2","Yes\n3\n3 0\n1 2\n3 0\n\nThere is no need to minimize the number of operations."]],"created_at":"2026-03-03 11:01:13"}}