E - Greedy Takahashi 2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 800 点

問題文

正整数 N と、(1,2,\dots,N) の順列 P が与えられます。

頂点に 1,2,\dots,N と番号がついた N 頂点の木があるとき、すぬけくんと高橋くんは以下の規則で動きます。

  • すぬけくんは、高橋くんが以下の規則に従って動いたときに返す数列が辞書順で最大になるように (1,2,\dots,N) の順列 Q を指定する。
  • 木の頂点 1 にいる高橋くんは、まずすぬけくんから Q を受け取り、整数列 R を長さ 1 の列 (Q_1) で初期化する。その後 N-1 回次のように動き、最終的な R を返す。
    • 過去に訪れたことのある頂点に隣接しているがまだ訪れていない頂点であって、最も Q_i が小さい頂点 i を訪れる（このような頂点は常にただ 1 つ存在することが証明できる）。その後、R の末尾に Q_i を追加する。

ただし、頂点 1 ははじめに訪れたものとみなします。

高橋くんが P を返すような木が存在するか判定してください。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

  • 1 \le T \le 10^5
  • 1 \le N \le 2 \times 10^5
  • P は (1,2,\dots,N) の順列
  • 全てのテストケースにおける N の総和は 2 \times 10^5 以下
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

各テストケースは以下の形式で与えられる。

N
P_1 P_2 \ldots P_N

出力

T 行出力せよ。

i 行目には i 番目のテストケースについて、条件を満たす木が存在するならば Yes 、そうでないならば No を出力せよ。

入力例 1

3
4
4 2 3 1
4
4 1 3 2
11
11 8 9 6 7 10 3 4 5 1 2

出力例 1

Yes
No
Yes

1 番目のテストケースについて、頂点 1-2 間、1-3 間、2-4 間に辺のある 4 頂点の木が条件を満たします。

すぬけくんが Q=(4,3,2,1) を指定すると、高橋くんは頂点 1,3,2,4 の順に動き、R=(4,2,3,1) が返されます。すぬけくんが Q をどのように指定しても、辞書順で (4,2,3,1) よりも大きい数列が高橋くんから返されるようにはできないので、結局返される数列は (4,2,3,1) です。

2 番目のテストケースについて、条件を満たす木は存在しないことが証明できます。

Score : 800 points

Problem Statement

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.

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.

Input

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

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 Input 1

3
4
4 2 3 1
4
4 1 3 2
11
11 8 9 6 7 10 3 4 5 1 2

Sample Output 1

Yes
No
Yes

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.