まず、\(2\) つの山を固定したときのスコアの最小値を求めます。 山にあるカードの番号を上から順に \(A_1, \ldots, A_N\) とし、 もう一方の山にあるカードの番号を上から順に \(B_1, \ldots, B_N\) とします。 前者の山を山 \(A\)、後者を山 \(B\) と呼ぶことにします。

カード \(2N\) が山 \(B\) に含まれるとします。 このとき、各 \(1 \leq i \leq N\) について \(A_i < B_j\) なる最小の \(j\) をとることができます。 \(j-i\) の最大値を \(d\) とします。このとき、求める値は \(N+d\) となります。 \(j-i=d\) となる \(i\) をとると、山 \(B\) からカードを \(d\) 枚以上取り除かなければカード \(A_i\) を取り除くことはできないので、 山 \(A\) を空にするためには、確かに \(N+d\) 回以上の操作が必要です。 一方で、\(d>0\) ならば \(j-i>0\) なる \(i\) のうち最小のものを、\(d=0\) ならば \(j-i=0\) なる \(i\) のうち最大のものを選び、 \(k=i\) として操作を行うことで、山 \(A\) の枚数を \(1\) 減らすか \(d\) を \(1\) 減らすことができます。 これより、スコアの最小値が \(N+d\) であることが示されました。

次に、この値の期待値を求めます。 各 \(0 \leq d \leq N-1\) について、スコアの最小値が \(N+d\) 以下となる確率を \(p(d)\) とします。 このとき、求める期待値は \(2N - \sum_{d=0}^{N-1} p(d)\) です。よって、\(p(d)\) が求まればよいです。

先程と同様に \(2\) つの山を固定し \(A_1,\ldots,A_N,B_1,\ldots,B_N\) を定めます。 \(2N\) が \(B_1,\ldots,B_N\) の中に含まれるとき、スコアの最小値が \(N+d\) 未満となる条件は以下のように表せます。

• 各 \(1 \leq i \leq N\) について、\(B_1, \ldots, B_{\min\{N,i+d\}}\) の中に \(A_i\) より大きい値が存在する。

\(A_1,\ldots,A_N,B_1,\ldots,B_N\) がこの条件を満たす確率は次の値です。

\(\prod_{1 \leq i \leq N-d} \frac{2i+d-1}{2i+d} \times \prod_{N-d < i \leq N} \frac{N+i-1}{N+i}\)

\(p(d)\) はこの値の \(2\) 倍であるので、\(p(1), \ldots, p(N)\) は線形時間で求めることができます。 よって、全体としても線形時間でこの問題を解くことができます。