{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"The 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$"},{"iden":"sample input 1","content":"3\n3\n2 3 1\n4\n4 3 2 1\n1\n1"},{"iden":"sample output 1","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}