{"problem":{"name":"Greedy Takahashi 2","description":{"content":"You are given a positive integer $N$ and a permutation $P$ of $(1,2,\\dots,N)$. When there is a tree with $N$ vertices numbered $1,2,\\dots,N$, Snuke and Takahashi move according to the following rules:","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc211_e"},"statements":[{"statement_type":"Markdown","content":"You are given a positive integer $N$ and a permutation $P$ of $(1,2,\\dots,N)$.\nWhen there is a tree with $N$ vertices numbered $1,2,\\dots,N$, Snuke and Takahashi move according to the following rules:\n\n*   Snuke specifies a permutation $Q$ of $(1,2,\\dots,N)$ such that the sequence returned by Takahashi, when following the rules below, is lexicographically maximum.\n*   Takahashi, who is at vertex $1$ of the tree, first receives $Q$ from Snuke and initializes an integer sequence $R$ with the length-$1$ sequence $(Q_1)$. Then, he moves $N-1$ times as follows, and returns the final $R$:\n    *   Visit the vertex $i$ with the smallest $Q_i$ among vertices that are adjacent to a previously visited vertex but have not yet been visited (it can be proved that there is always exactly one such vertex). Then, append $Q_i$ to the end of $R$.\n\nHere, vertex $1$ is considered to have been visited initially.\nDetermine whether there exists a tree such that Takahashi returns $P$.\nYou are given $T$ test cases; solve each of them.\n\n## Constraints\n\n*   $1 \\le T \\le 10^5$\n*   $1 \\le N \\le 2 \\times 10^5$\n*   $P$ is a permutation of $(1,2,\\dots,N)$.\n*   The sum of $N$ over all test cases is at most $2 \\times 10^5$.\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$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nEach test case is given in the following format:\n\n$N$\n$P_1$ $P_2$ $\\ldots$ $P_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc211_e","tags":[],"sample_group":[["3\n4\n4 2 3 1\n4\n4 1 3 2\n11\n11 8 9 6 7 10 3 4 5 1 2","Yes\nNo\nYes\n\nFor the first test case, a tree with four vertices having edges between vertices $1$\\-$2$, $1$\\-$3$, and $2$\\-$4$ satisfies the conditions.\nIf Snuke specifies $Q=(4,3,2,1)$, Takahashi visits vertices $1,3,2,4$ in this order and returns $R=(4,2,3,1)$. No matter what $Q$ Snuke specifies, it is impossible to make Takahashi return a sequence lexicographically larger than $(4,2,3,1)$, so the sequence that ends up being returned is $(4,2,3,1)$.\nFor the second test case, it can be proved that there is no tree satisfying the conditions."]],"created_at":"2026-03-03 11:01:14"}}