{"problem":{"name":"Non-Overlapping Swaps","description":{"content":"You are given a permutation $P=(P_1,P_2,\\cdots,P_N)$ of $(1,2,\\cdots,N)$. Find one sequence of integer pairs $((l_1,r_1),(l_2,r_2),\\cdots,(l_k,r_k))$ that satisfies all of the following conditions. *","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"wtf22_day1_b"},"statements":[{"statement_type":"Markdown","content":"You are given a permutation $P=(P_1,P_2,\\cdots,P_N)$ of $(1,2,\\cdots,N)$.\nFind one sequence of integer pairs $((l_1,r_1),(l_2,r_2),\\cdots,(l_k,r_k))$ that satisfies all of the following conditions.\n\n*   The length $k$ of the sequence satisfies $0 \\leq k \\leq N-1$.\n*   $1 \\leq l_i \\leq r_i \\leq N$ ($1 \\leq i \\leq k$).\n*   For each $1 \\leq i \\leq k-1$, it holds that $r_{i+1} \\leq l_i$ or $r_i \\leq l_{i+1}$.\n*   Performing the following $k$ operations sorts $P$ in ascending order.\n    *   The $i$\\-th operation: swap the values of $P_{l_i}$ and $P_{r_i}$. If $l_i=r_i$, do nothing.\n\nIt can be proved that such a sequence always exists under the constraints of this problem.\nProcess $T$ test cases for each input file.\n\n## Constraints\n\n*   $1 \\leq T \\leq 250000$\n*   $1 \\leq N \\leq 250000$\n*   $P=(P_1,P_2,\\cdots,P_N)$ is a permutation of $(1,2,\\cdots,N)$.\n*   The sum of $N$ for each input file is at most $250000$.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$case_1$\n$case_2$\n$\\vdots$\n$case_T$\n\nEach test case $case_i$ is in the following format:\n\n$N$\n$P_1$ $P_2$ $\\cdots$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"wtf22_day1_b","tags":[],"sample_group":[["3\n3\n2 3 1\n4\n4 3 2 1\n1\n1","2\n2 3\n1 2\n3\n1 4\n1 1\n2 3\n0\n\nLet us explain the first test case.\nThe sample output satisfies all of the conditions. For example, the fourth condition can be verified as follows: $P=(2,3,1)\\to$(swap $P_2,P_3$)$\\to(2,1,3)\\to$(swap $P_1,P_2$)$\\to(1,2,3)$．\nThe following output, on the other hand, is not correct:\n\n2\n1 2\n1 3\n\nThis is because the third condition is not satisfied."]],"created_at":"2026-03-03 11:01:13"}}