{"problem":{"name":"Nearer Permutation","description":{"content":"In this problem, a \"permutation\" always means a permutation of $(1,2,\\cdots,N)$. For two permutations $p$ and $q$, let us define the distance between them, $d(p,q)$, as follows. *   Consider making $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc058_e"},"statements":[{"statement_type":"Markdown","content":"In this problem, a \"permutation\" always means a permutation of $(1,2,\\cdots,N)$.\nFor two permutations $p$ and $q$, let us define the distance between them, $d(p,q)$, as follows.\n\n*   Consider making $p$ equal $q$ by repeatedly swapping two adjacent terms in $p$. Let $d(p,q)$ be the minimum number of swaps required here.\n\nAdditionally, for a permutation $x$, let us define another permutation $f(x)$ as follows.\n\n*   Let $y=(1,2,\\cdots,N)$. Consider permutations $z$ such that $d(x,z) \\leq d(y,z)$. Let $f(x)$ be the lexicographically smallest of those permutations.\n\nFor example, when $x=(2,3,1)$, the permutations $z$ such that $d(x,z) \\leq d(y,z)$ are $z=(2,1,3),(2,3,1),(3,1,2),(3,2,1)$. The lexicographically smallest of them is $(2,1,3)$, so we have $f(x)=(2,1,3)$.\nYou are given a permutation $A=(A_1,A_2,\\cdots,A_N)$. Determine whether there is a permutation $x$ such that $f(x)=A$.\nSolve $T$ test cases for each input file.\nWhat is lexicographical order on sequences?The algorithm described here determines the lexicographical order between distinct sequences $S$ and $T$.\nBelow, let $S_i$ denote the $i$\\-th element of $S$. Additionally, let $S \\lt T$ and $S \\gt T$ mean \"$S$ is lexicographical smaller than $T$\" and \"$S$ is lexicographical larger than $T$,\" respectively.\n\n1.  Let $L$ be the length of the shorter of $S$ and $T$. For each $i=1,2,\\dots,L$, let us check whether $S_i$ and $T_i$ are equal.\n2.  If there is $i$ such that $S_i \\neq T_i$, let $j$ be the smallest such $i$, and compare $S_j$ and $T_j$. If $S_j$ is smaller than $T_j$ (as a number), we conclude $S \\lt T$ and exit; if $S_j$ is larger than $T_j$, we conclude $S \\gt T$ and exit.\n3.  If there is no $i$ such that $S_i \\neq T_i$, compare the lengths of $S$ and $T$. If $S$ is shorter than $T$, we conclude $S \\lt T$ and exit; if $S$ is longer than $T$, we conclude $S \\gt T$ and exit.\n\n## Constraints\n\n*   $1 \\leq T \\leq 150000$\n*   $2 \\leq N \\leq 300000$\n*   $(A_1,A_2,\\cdots,A_N)$ is a permutation of $(1,2,\\cdots,N)$.\n*   The sum of $N$ in one input file does not exceed $300000$.\n*   All values in input are integers.\n\n## Input\n\nInput 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 case is in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc058_e","tags":[],"sample_group":[["2\n2\n1 2\n2\n2 1","Yes\nYes\n\nFor instance, when $A=(2,1)$, one can let $x=(2,1)$ to satisfy $f(x)=A$."],["6\n3\n1 2 3\n3\n1 3 2\n3\n2 1 3\n3\n2 3 1\n3\n3 1 2\n3\n3 2 1","Yes\nYes\nYes\nYes\nNo\nNo\n\nFor instance, when $A=(2,3,1)$, one can let $x=(3,2,1)$ to satisfy $f(x)=A$."],["24\n4\n1 2 3 4\n4\n1 2 4 3\n4\n1 3 2 4\n4\n1 3 4 2\n4\n1 4 2 3\n4\n1 4 3 2\n4\n2 1 3 4\n4\n2 1 4 3\n4\n2 3 1 4\n4\n2 3 4 1\n4\n2 4 1 3\n4\n2 4 3 1\n4\n3 1 2 4\n4\n3 1 4 2\n4\n3 2 1 4\n4\n3 2 4 1\n4\n3 4 1 2\n4\n3 4 2 1\n4\n4 1 2 3\n4\n4 1 3 2\n4\n4 2 1 3\n4\n4 2 3 1\n4\n4 3 1 2\n4\n4 3 2 1","Yes\nYes\nYes\nYes\nYes\nYes\nYes\nYes\nYes\nYes\nNo\nNo\nNo\nNo\nNo\nNo\nNo\nNo\nNo\nNo\nNo\nNo\nNo\nNo"]],"created_at":"2026-03-03 11:01:14"}}