\(A_i<B_i\) および \(B_i < B_{i+1}\) としても一般性を失わないので、この大小関係を仮定します。 このとき、箱の列 \(p_1,\ldots,p_N\) に対して問題文の条件を整理すると、以下のいずれかを満たすことと同値であることが分かります。

• すべての \(1 \leq i < N\) に対して \(B_{p_i} > A_{p_{i+1}}\)
• ある \(i\) に対して \(B_{p_i} < A_{p_{i+1}}\) となり、\(1 \leq j < i\) では \(B_{p_j} > A_{p_{j+1}}\)、\(i < j < N\) では \(A_{p_j} < B_{p_{j+1}}\) となる。

各箱 \(i\) について、\(j>i\) かつ \(A_j<B_i\) なる \(i\) の個数を \(U_i\) とします。 このとき、前者の条件を満たす列の個数は、番号の大きい箱から順に挿入していくことで、 \(\prod_{1 \leq i \leq N} (U_i+1)\) と分かります。次に、後者の条件を満たす列の個数を求めます。

\(B_b < A_a\) なる \((b,a)\) を固定し、ある \(i\) について \((p_i, p_{i+1}) = (b,a)\) となる後者の条件を満たす \(p\) の個数を求めます。 先と同様にして、番号の大きい箱から順に挿入していくと、求める個数は \(\prod_{1 \leq i < b} U_i \times \prod_{b<i<a} (U_i+1) \times \prod_{a< i \leq N} (U_i+2)\) と分かります。 この値を \((b,a)\) すべてについて求められればよいです。これは累積和を用いることで線形時間で計算できます。