任意の \(2\) 要素の比較を行なってマージソートをする方法が考えられますが、 \(N=100\) の場合では \(500\) 回の質問に間に合いません。
実際、 \(N\) 要素をソートする比較ソートアルゴリズムの比較回数の下界は \(\lceil\) \(\mathrm{log}_2\) \((N !)\) \(\rceil\) であることが知られており、 \(N=100\) のときこの値は \(525\) になります。

ジャッジの回答で「=」が返ってきた場合を上手く利用する方法を考えます。

以下、数列において index が小さい方を「前」、大きい方を「後ろ」と表現することにします。

次の性質を用います。

• \(Q\) において、 \((Q_L,Q_{L+1},\cdots,Q_R)\) の部分を \((Q_{L+1},\cdots,Q_R,Q_{L})\) のようにローテーションしたものを \(Q'\) とする。
  \(\mathrm{dist}(P,Q)\) と \(\mathrm{dist}(P,Q')\) の大小関係によって、\(Q_L\) の位置が \(Q_L, Q_{L+1}, \cdots , Q_R\) の中で前半、後半、中央のいずれに位置するべきかが分かる。

例えば \((1,2,3,4,5)\) を \((2,3,4,5,1)\) にして必要な swap 回数が増えたとすると、\(2,3,4,5\) の中で、\(1\) より後ろにあるべきものが、\(1\) より前にあるべきものより多いことが分かります。swap 回数が減った場合も同様です。swap 回数が変わらなかった場合は、\(1\) より後ろにあるべきものと \(1\) より前にあるべきもの数が同じ、つまり \(1\) が中央に位置するべきだと分かります。

これを各要素について調べることで、 \(N\) が奇数の場合は数列を「前半分」「中央」「後ろ半分」に分けることができ、長さ \(\frac{N-1}{2},1,\frac{N-1}{2}\) の \(3\) つの数列に分割することができます。

\(N\) が偶数の場合でも、最初に後ろ \(N-1\) 個の要素でローテーションを行い、最後に最前の要素にローテーションを行うことで、長さ \(\frac{N}{2},1,\frac{N}{2}-1\) の \(3\) つの数列に分割することができます。

数列を分割したあとはクイックソートの要領で再帰的にソートを行なっていけば良いです。
長さ \(x\) の順列を特定するのに必要な質問回数を \(f(x)\) とすると、以下の漸化式が成り立ちます。

• \(f(x)= (x-1) + f( \lceil \frac{x-1}{2} \rceil) + f( \lfloor \frac{x-1}{2} \rfloor)\)
• \(f(0) = 0\)

\(x-1\) 個の要素の位置を特定すれば、残りの \(1\) つの位置も分かります ( 実際にはもっと少ない回数で特定可能なこともあります ) 。分割後は再帰的に計算します。

実際はこれに加えて、最初の比較の対象となる「\(1\) 回目の質問」を数列ごとに行う必要がありますが、これは再帰の深さごとにまとめて良いです。

\(N \leq 100\) であるため、この問題は \(f(100) + \lceil \mathrm{log}_2 100 \rceil =487\) 回の質問で解くことができました。