本解では順列を \(P_i\) と \(P_{N-i}\) の小さなブロックに分けていましたが、実は大きなブロックに分けても解くことができます。

\(N=4M\) の場合の構築法を最初に説明します。以下のように構築をすれば良いです。

• \((3m,3m-1,\dots,2m+1),(1,2,\dots,m),(3m+1,3m+2,\dots,4m),(2m,2m-1,\dots,m+1)\) をこの順に連結した列を \(P\) とする。

実は、それ以外の場合もこの構築を少し改変することで構築できます。

\(N=4M+1\) の場合を考えます。以下のように構築をすれば良いです。

• \((3m+1,3m,\dots,2m+2),(1,2,\dots,m),(2m+1),(3m+2,3m+3,\dots,4m+1),(2m,2m-1,\dots,m+1)\) をこの順に連結した列を \(P\) とする。

\(N=4M+2\) の場合を考えます。実は、\(N=4M\) の場合の構築の全要素に \(1\) を加算したものを考え、その末尾に \((1,N)\) を挿入したものが条件を満たします。証明は、元の構築の転倒数を具体的に考えると良いです。

\(N=4M+3\) の場合も全く同様で、\(N=4M+1\) の末尾に適切に要素を挿入すれば良いです。よって、この問題を \(O(N)\) で解くことが出来ました。