First, let us find the minimum score for a fixed pair of two piles. Let \(A_1, \ldots, A_N\) be the ID numbers of one pile (call it Pile \(A\)) from top to bottom, and \(B_1, \ldots, B_N\) be the ID numbers of another pile (call it Pile \(B\)) from top to bottom.

Assume that Card \(2N\) is in Pile \(B\). Then, for each \(1 \leq i \leq N\), we can take the minimum \(j\) such that \(A_i < B_j\). Let \(d\) be the maximum value of \(j - i\). Then, it turns out that the minimum score is \(N+d\). We do need at least \(N+d\) operations, since if we take \(i\) such that \(j-i=d\), we have to remove \(d\) or more cards from Pile \(B\) to remove Card \(A_i\). On the other hand, we can always remove one card from Pile \(A\) or decrease \(d\) by \(1\), by choosing the minimum \(i\) such that \(j-i>0\) if \(d>0\) and choosing the maximum \(i\) such that \(j-i=0\) if \(d=0\) and doing the operation with \(k=i\). Now, we have shown that the minimum score is \(N+d\).

Next, let us find the expected value of this. For each \(0 \leq d \leq N-1\), let \(p(d)\) be the probability that the minimum score is at most \(N+d\). Then, the expected value we seek is \(2N - \sum_{d=0}^{N-1} p(d)\), so we just have to \(p(d)\).

Again, let us fix the pair of two piles and assume that \(A_1,\ldots,A_N,B_1,\ldots,B_N\) are constant. If \(2N\) is among \(B_1, \ldots, B_N\), the minimum score is less than \(N+d\) if and only if:

• for each \(1 \leq i \leq N\), there is a value greater than \(A_i\) among \(B_1, \ldots, B_{\min\{N,i+d\}}\).

The probability that \(A_1,\ldots,A_N,B_1,\ldots,B_N\) satisfy this condition is:

\(\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)\) is the above value multiplied by \(2\), so we can find \(p(1), \ldots, p(N)\) in linear time. Thus, we can solve the whole problem in linear time, too.