\(x\) の適当な \(2\) 項を swap することを考えます． これは同時に \(y\) を swap することにも対応します． 一度の swap によって，\(f(x)\) の値は \(\pm 1\) だけ変化し，また \(f(y)\) の値も \(\pm 1\) だけ変化します．

よって，\(x\) によらず，\(f(x)+f(y)\) の値の偶奇が一定であることがわかります． 以下，\(K\) がこの偶奇の条件を満たしているものとして考えます．

\(f(x)+f(y)\) の最大値を考えます． これは，\(x=(1,2,\cdots,N)\) で達成可能です． \(f(x)<N\) となる \(x\) で最大値を達成している場合，\(f(x)\) の値を \(+1\) するような swap が可能です． これで，\(f(x)+f(y)\) の値を減らすことなく，\(f(x)\) の値がより大きな解が得られます． この操作を繰り返すことで，\(f(x)=N\) となる解，つまり \(x=(1,2,\cdots,N)\) となる解を得られます．

\(f(x)+f(y)\) の最小値を考えます． これは \(2\) か \(3\) (偶奇によって変化) であることがわかります． 具体的には，以下の方法で解を構成できます．

• \(N\) 頂点からなるグラフ \(G,H\) を用意する．
• \(i=1,2,N-2\) について，この順に，\(x_i\) として以下の条件をみたす値 \(v\) を採用する．そして，\(G\) に辺 \((i,v)\) を，\(H\) に辺 \((i,P_v)\) を追加する．
  • 現在，\(G\) において頂点 \(i\) と頂点 \(v\) が非連結
  • 現在，\(H\) において頂点 \(i\) と頂点 \(P_v\) が非連結
• \(i=N-1\) について，\(x_i\) として以下の条件を満たす値 \(v\) を採用する．
  • 現在，\(G\) において頂点 \(i\) と頂点 \(v\) が非連結

上記の操作が行える，つまり常に条件を満たす \(v\) が取れることは，次のように確認できます． \(G\) は常にパスとサイクルの集合であり，\(G\) について条件を満たさない \(v\) は \(1\) つしかありません． \(H\) についても同様です． よって，\(v\) として使える値の候補が \(3\) つあれば必ず両方の条件を満たすものを発見できます． \(i=N-1\) についても同様です．

上記の操作で作られるサイクルの個数が \(3\) 以下であることは明らかです． よって， \(f(x)+f(y)\) の最小値は \(2\) または \(3\) です．

以下，\(K\) が \(f(x)+f(y)\) の最小，最大の間に入っているものとします．

\(f(x)+f(y)\) を最大化する \(x\) を \(xmax\)，最小化する \(x\) を \(xmin\) と置くことにします． 適当な \(2\) 項の swap を繰り返すことで \(xmax\) を \(xmin\) に変化させる操作列を適当に一つとり，\(xmax=A_0 \to A_2 \to \cdots \to A_s = xmin\) と置きます．ここで，操作回数 \(s\) は \(O(N)\) であればなんでもよいです．

\(x=A_i\) としたときの \(f(x)+f(y)\) の値を \(g(i)\) と置くことにします． \(g(i+1)-g(i)=-2,0,2\)，\(g(0) \geq K \geq g(s)\)，\(K \equiv g(i) \mod 2\) より，\(K=g(i)\) をみたす \(i\) が必ず存在します． そしてこの \(i\) は二分探索で見つけることができます． \(g(i)\) の計算は \(O(N)\) で行えるので，全体で \(O(N \log N)\) で答えが求まります．

解答例