便利のため，添字，値を共に \(0\)-based で考えます．

まず \(f(x)\) を求める方法を考えます．

\(z=x\) を基準解として，\(z\) の要素を先頭から決めていくことを考えます． \(d(x,z) \leq d(y,z)\) という条件の元で，できるだけ小さい値を先頭に移動させればよいです． \(x\) の転倒数を \(Invs\) とすると，結局以下のようなアルゴリズム（以降アルゴリズム A と呼ぶことにする）が得られます．

• \(result=(),s=Invs/2\) とする．
• 以下の操作（以降操作 X と呼ぶことにする）を \(N\) 回行う．
  • \(x_0,x_1,\cdots,x_{\min(floor(s),N-1)}\) のうちで最小のものを \(x_m\) とおく．
  • result の末尾に \(x_m\) を追加する．
  • \(x\) から \(x_m\) を削除する．（残った要素の添字をつけ直す）
  • \(s:=s-m\) とする．
• \(result\) を返す．

\(A_k>A_{k+1}\) となる最小の添字 \(k\) を取ります． そのような \(k\) がない場合，答えは明らかに Yes です．

上記の操作の様子を考えると，操作 X を \(k\) 回行った後の \(x\) は以下の性質を満たしているとわかります．

• \(x\) の \(0\) 番目の要素は \(A_k\) であり，\(x\) の \((floor(s)+1)\) 番目の要素は \(A_{k+1}\) である．また，\(\min(x_0,x_1,\cdots,x_{floor(s)})=x_0\) である．

• \(x\) から \(A_{k+1}\) を除くと，\(A_k,A_{k+2},A_{k+3},\cdots,A_{N-1}\) がこの順に並んでいる．

以上より，\(f(x)=A\) を満たす順列 \(x\) は，以下の手順で得られるものに限られるとわかります．

• \(B=A\) とする．
• \(i=k+1,k-1,k-2,\cdots,0\) について，以下の操作を行う．
  • \(B_i\) を右にいくつか移動させる．より正確には，\(t\) 個分移動させるならば，\(B_i,B_{i+1},\cdots,B_{i+t}\) を \(B_{i+1},\cdots,B_{i+t},B_i\) に変更する． この時，（操作前の段階で）\(B_i < B_{i+j}\) (\(1 \leq j \leq t\)) が成り立つ必要がある．\(i=k+1\) の場合だけは更に，\(A_k < B_{i+j}\) も必要である．

各 \(i\) について，\(B_i\) を移動させた量を \(c_i\) で表すことにします． \(c_i\) をうまく調整することで，アルゴリズム A の出力が目標と一致すればよいです．

操作 X を \(k+1\) 回行った後に，\(A_{k+1}\) の値がある位置 \(p\) と \(s\) の値の差（この値を \(v=s-p\) とおく）がいくつになるか考えます．

まず，\(i \neq k+1\) について考えます． \(c_i\) が \(1\) 増えると，\(s\) の初期値が \(1/2\) 増加し，また \(i\) 回目の操作で選ぶ \(m\) の値が \(1\) 増えるので，合計で \(s\) の値は \(1/2\) 減少し，\(v\) の値は \(1/2\) 減ることになります．

\(i = k+1\) の場合は，\(s\) の初期値が \(1/2\) 増加し，\(p\) の値が \(1\) 増えるので，\(v\) の値は \(1/2\) 減ることになります．

結局どちらの場合でも \(v\) は \(1/2\) 減ります． \(A\) の転倒数を \(S\) とおくと，\(c_i\) が全て \(0\) のときは \(v=S/2\) であり，目標とする \(v\) の値が \(0\) または \(1/2\) なので，\(c_i\) の総和を \(S\) または \(S-1\) にすべきだとわかります．

そこで，この \(2\) 通りの値を両方試してみることにします． （なお，実は \(S-1\) のケースだけ考えれば十分であることが示せます）

\(c_i\) の総和がわかっているので，\(x\) の転倒数もわかっています． ここで，\(c_i\) の値を，”\(A_i\) の昇順” で決めていくことにすると，できるだけ大きい値にする貪欲がうまく働きます． これは，上記の戦略に沿わない解が存在するとしても，それをうまく組み替えて上記の戦略に沿った解に変形できることから従います． この証明の詳細は単純な場合分けなので割愛します．

上記の戦術に従って実際に \(c_i\) を決定していって，途中で矛盾が発生したり，総和が最初に決めた値に届かなかったりする場合は No，そうでない場合は Yes と判定できます．

計算量は転倒数の計算がボトルネックになり，\(O(N \log N)\) です．

解答例(c++)