数列の各値が中央値として数えられる回数を求めればよいです。これは主客転倒などと呼ばれている考え方です。

数列の各値を \(2\) つの値の組 \(P=(P^\mathrm{val},P^\mathrm{alp})\) に変換しておきます。具体的には \(A_i\) は \((A_i, \)A\()\) のように、数列の値とどの数列の値であるかの情報を持っておきます。次に \(5N\) 個の組をまとめてソートします（数列の値が昇順に並べ替えられていれば、他の値の順序はなんでもよいです）。\(5\) つの組の中央値をソート後の列 \(F\) における真ん中に位置する組と定義すれば元の問題は次のように言い換えられます。

• \(1\le i\lt j\lt k\lt l\lt m\le 5N\) かつ \(\lbrace F_{i}^\mathrm{alp},F_{j}^\mathrm{alp},F_{k}^\mathrm{alp},F_{l}^\mathrm{alp},F_{m}^\mathrm{alp}\rbrace = \lbrace \) A ,B, C, D, E \(\rbrace\) を満たす \((i,j,k,l,m)\) すべてに対する \(F_{k}^\mathrm{val}\) の総和を求めよ。

言い換え後の問題は主客転倒の問題としては典型的です。\(F\) を左右一列に並べます。 左から順に見て、今見ている組より左および右にある各 \(\mathrm{alp}\) を持つ組の個数をそれぞれ持っておくことで、各組の \(\mathrm{val}\) の値が何回数えられるか（つまり、総和への寄与）を正しく計算できます。

計算量は \(\mathrm{O}(N \log N)\) です。

実装例(python)

実装例(C++)