AT_arc211_e [ARC211E] Greedy Takahashi 2

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: - 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. - 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 $ : - 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 $ . Here, vertex $ 1 $ is considered to have been visited initially. Determine whether there exists a tree such that Takahashi returns $ P $ . You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $

Output $ T $ lines. The $ i $ -th line should contain `Yes` if there exists a tree satisfying the conditions for the $ i $ -th test case, and `No` otherwise.

### Sample Explanation 1 For the first test case, a tree with four vertices having edges between vertices $ 1 $ - $ 2 $ , $ 1 $ - $ 3 $ , and $ 2 $ - $ 4 $ satisfies the conditions. If 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) $ . For the second test case, it can be proved that there is no tree satisfying the conditions. ### Constraints - $ 1 \le T \le 10^5 $ - $ 1 \le N \le 2 \times 10^5 $ - $ P $ is a permutation of $ (1,2,\dots,N) $ . - The sum of $ N $ over all test cases is at most $ 2 \times 10^5 $ . - All input values are integers.