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