E - Nearer Permutation Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1400 点

問題文

この問題では，順列と言った際には，(1,2,\cdots,N) の順列を指すものとします．

2 つの順列 p,q に対し，それらの距離 d(p,q) を次のように定義します．

  • p の中で隣接 2 項を swap することを繰り返し，p を q に一致させることを考える．この時必要な最小の操作回数を d(p,q) とする．

さらに，順列 x に対し，順列 f(x) を次のように定義します．

  • y=(1,2,\cdots,N) とする．ここで，順列 z であって，d(x,z) \leq d(y,z) を満たすものを考える． これらの中で辞書順最小のものを f(x) とする．

例えば，x=(2,3,1) の場合，d(x,z) \leq d(y,z) を満たす順列としては，z=(2,1,3),(2,3,1),(3,1,2),(3,2,1) が考えられます． このうち辞書順最小なのは (2,1,3) なので， f(x)=(2,1,3) となります．

順列 A=(A_1,A_2,\cdots,A_N) が与えられます． f(x)=A を満たす順列 x が存在するかどうか判定してください．

1 つの入力ファイルにつき，T 個のテストケースを解いてください．

数列の辞書順とは？

相異なる数列 S と数列 T の大小を判定するアルゴリズムを以下に説明します。

以下では S の i 番目の要素を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

  1. S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
  2. S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j が T_j より（数として）小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
  3. S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

制約

  • 1 \leq T \leq 150000
  • 2 \leq N \leq 300000
  • (A_1,A_2,\cdots,A_N) は (1,2,\cdots,N) の順列
  • 1 つの入力ファイルにつき，N の総和は 300000 を超えない
  • 入力される値はすべて整数である

入力

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

T
case_1
case_2
\vdots
case_T

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

N
A_1 A_2 \cdots A_N

出力

各ケースに対し，f(x)=A を満たす順列 x が存在するならば Yes を，存在しないならば No を出力せよ．

入力例 1

2
2
1 2
2
2 1

出力例 1

Yes
Yes

例えば A=(2,1) の場合は，x=(2,1) とすると f(x)=A となります．

入力例 2

6
3
1 2 3
3
1 3 2
3
2 1 3
3
2 3 1
3
3 1 2
3
3 2 1

出力例 2

Yes
Yes
Yes
Yes
No
No

例えば A=(2,3,1) の場合は，x=(3,2,1) とすると，f(x)=A となります．

入力例 3

24
4
1 2 3 4
4
1 2 4 3
4
1 3 2 4
4
1 3 4 2
4
1 4 2 3
4
1 4 3 2
4
2 1 3 4
4
2 1 4 3
4
2 3 1 4
4
2 3 4 1
4
2 4 1 3
4
2 4 3 1
4
3 1 2 4
4
3 1 4 2
4
3 2 1 4
4
3 2 4 1
4
3 4 1 2
4
3 4 2 1
4
4 1 2 3
4
4 1 3 2
4
4 2 1 3
4
4 2 3 1
4
4 3 1 2
4
4 3 2 1

出力例 3

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No

Score : 1400 points

Problem Statement

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 p equal q by repeatedly swapping two adjacent terms in p. Let d(p,q) be the minimum number of swaps required here.

Additionally, for a permutation x, let us define another permutation f(x) as follows.

  • 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.

For 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).

You are given a permutation A=(A_1,A_2,\cdots,A_N). Determine whether there is a permutation x such that f(x)=A.

Solve T test cases for each input file.

What is lexicographical order on sequences?

The algorithm described here determines the lexicographical order between distinct sequences S and T.

Below, 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.

  1. 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.
  2. 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.
  3. 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.

Constraints

  • 1 \leq T \leq 150000
  • 2 \leq N \leq 300000
  • (A_1,A_2,\cdots,A_N) is a permutation of (1,2,\cdots,N).
  • The sum of N in one input file does not exceed 300000.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

T
case_1
case_2
\vdots
case_T

Each case is in the following format:

N
A_1 A_2 \cdots A_N

Output

For each case, print Yes if there is a permutation x such that f(x)=A, and No otherwise.

Sample Input 1

2
2
1 2
2
2 1

Sample Output 1

Yes
Yes

For instance, when A=(2,1), one can let x=(2,1) to satisfy f(x)=A.

Sample Input 2

6
3
1 2 3
3
1 3 2
3
2 1 3
3
2 3 1
3
3 1 2
3
3 2 1

Sample Output 2

Yes
Yes
Yes
Yes
No
No

For instance, when A=(2,3,1), one can let x=(3,2,1) to satisfy f(x)=A.

Sample Input 3

24
4
1 2 3 4
4
1 2 4 3
4
1 3 2 4
4
1 3 4 2
4
1 4 2 3
4
1 4 3 2
4
2 1 3 4
4
2 1 4 3
4
2 3 1 4
4
2 3 4 1
4
2 4 1 3
4
2 4 3 1
4
3 1 2 4
4
3 1 4 2
4
3 2 1 4
4
3 2 4 1
4
3 4 1 2
4
3 4 2 1
4
4 1 2 3
4
4 1 3 2
4
4 2 1 3
4
4 2 3 1
4
4 3 1 2
4
4 3 2 1

Sample Output 3

Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
No
No
No
No
No
No
No
No
No
No
No
No
No