\(A_i \gt K/2\) であるグループ \(G_1\) とそうでないグループ \(G_2\) に分けてそれぞれ降順にソートする.

\(G_1\) は必ず \(G_2\) としかペアが組めない.

\(G_1\) の大きい人から順に考える. \(i\) 番目に取り出したのレートを \(A_i\) とすると, この人と組める \(G_2\) 内の人の人数 \(B_i\) は二分探索で求められる. このうち \(i-1\) 人はすでにこれ以前に誰かと組んでるので, \(B_i - (i - 1)\) を掛けることになる.

これを \(G_1\) のすべての人について行い, 余った人は自由にペアを組めるので, 余った人数を \(m\) とすると \(\combi{n}{2} \cdot \combi{n-2}{2} \cdots \combi{2}{2} / (m/2)!\) を掛ければいい.