{"problem":{"name":"Sort Left and Right","description":{"content":"You are given a permutation $P=(P_1,P_2,\\dots,P_N)$ of $(1,2,\\dots,N)$. You want to satisfy $P_i=i$ for all $i=1,2,\\dots,N$ by performing the following operation zero or more times: *   Choose an int","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc181_a"},"statements":[{"statement_type":"Markdown","content":"You are given a permutation $P=(P_1,P_2,\\dots,P_N)$ of $(1,2,\\dots,N)$.\nYou want to satisfy $P_i=i$ for all $i=1,2,\\dots,N$ by performing the following operation zero or more times:\n\n*   Choose an integer $k$ such that $1 \\leq k \\leq N$. If $k \\geq 2$, sort the $1$\\-st through $(k-1)$\\-th terms of $P$ in ascending order. Then, if $k \\leq N-1$, sort the $(k+1)$\\-th through $N$\\-th terms of $P$ in ascending order.\n\nIt can be proved that under the constraints of this problem, it is possible to satisfy $P_i=i$ for all $i=1,2,\\dots,N$ with a finite number of operations for any $P$. Find the minimum number of operations required.\nYou have $T$ test cases to solve.\n\n## Constraints\n\n*   $1 \\leq T \\leq 10^5$\n*   $3 \\leq N \\leq 2 \\times 10^5$\n*   $P$ is a permutation of $(1,2,\\dots,N)$.\n*   All input values are integers.\n*   The sum of $N$ across the test cases in a single input is at most $2 \\times 10^5$.\n\n## Input\n\nThe input 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 given in the following format:\n\n$N$\n$P_1$ $P_2$ $\\dots$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc181_a","tags":[],"sample_group":[["3\n5\n2 1 3 5 4\n3\n1 2 3\n7\n3 2 1 7 5 6 4","1\n0\n2\n\nFor the first test case,\n\n*   Performing the operation with $k=1$ results in $P$ becoming $(2,1,3,4,5)$.\n    \n*   Performing the operation with $k=2$ results in $P$ becoming $(2,1,3,4,5)$.\n    \n*   Performing the operation with $k=3$ results in $P$ becoming $(1,2,3,4,5)$.\n    \n*   Performing the operation with $k=4$ results in $P$ becoming $(1,2,3,5,4)$.\n    \n*   Performing the operation with $k=5$ results in $P$ becoming $(1,2,3,5,4)$.\n    \n\nSpecifically, performing the operation with $k=3$ results in $P$ satisfying $P_i=i$ for all $i=1,2,\\dots,5$. Therefore, the minimum number of operations required is $1$.\nFor the third test case, performing the operation with $k=4$ followed by $k=3$ results in $P$ changing as $(3,2,1,7,5,6,4) \\rightarrow (1,2,3,7,4,5,6) \\rightarrow (1,2,3,4,5,6,7)$."]],"created_at":"2026-03-03 11:01:14"}}