east1016's Last Problem

問題文

teamLove株式会社は、人員削減のため、アウトプット量が不十分である社員を以下の方法で解雇していく方針を取ることにしました。

1. 全社員をシャッフルして $1$ 列に並べる。
2. 並べた社員を前から順に見ていき、見ている社員のアウトプット量が、現在解雇されていない社員のアウトプット量の中央値未満であれば即座に解雇する。

teamLove株式会社の現在の社員数 $N$ と、各社員のアウトプット量 $A_1, A_2, ..., A_N$ が整数で与えられます。

解雇される社員数の期待値を $\bmod \ 998244353$ で出力してください。

なお、長さ $L$ の数列 $B$ に対して、$B$ の中央値とは、 $B$ を昇順にソートして得られる数列を $B'$ として、$B'$ の $\left\lfloor \frac{L}{2} \right\rfloor + 1$ 番目の値のことを指します。

制約

• $1 \leq N \leq 2 \times 10^{5}$
• $1 \leq A_i \leq 3$
• 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力せよ。

サンプル

6
1 1 2 2 3 3

665496238

例として社員が $5, 3, 1, 2, 4, 6$ の順に並んだ場合に、解雇されるteamLove株式会社の社員数を考えます。

• 先頭から $1$ 番目の社員のアウトプット量は $A_5 = 3$ です。現在解雇されていない社員は $\{1, 2, 3, 4, 5, 6\}$ の $6$ 人なので、アウトプット量を昇順に並べると $\{1, 1, 2, 2, 3, 3\}$ です。この中央値は $2$ であり、$A_5 \geq 2$ なので、社員 $5$ は解雇されません。
• 先頭から $2$ 番目の社員のアウトプット量は $A_3 = 2$ です。現在解雇されていない社員は $\{1, 2, 3, 4, 5, 6\}$ の $6$ 人なので、アウトプット量を昇順に並べると $\{1, 1, 2, 2, 3, 3\}$ です。この中央値は $2$ であり、$A_3 \geq 2$ なので、社員 $3$ は解雇されません。
• 先頭から $3$ 番目の社員のアウトプット量は $A_1 = 1$ です。現在解雇されていない社員は $\{1, 2, 3, 4, 5, 6\}$ の $6$ 人なので、アウトプット量を昇順に並べると $\{1, 1, 2, 2, 3, 3\}$ です。この中央値は $2$ であり、$A_1 < 2$ なので、社員 $1$ は即座に解雇されます。
• 先頭から $4$ 番目の社員のアウトプット量は $A_2 = 1$ です。現在解雇されていない社員は $\{2, 3, 4, 5, 6\}$ の $5$ 人なので、アウトプット量を昇順に並べると $\{1, 2, 2, 3, 3\}$ です。この中央値は $2$ であり、$A_2 < 2$ なので、社員 $2$ は即座に解雇されます。
• 先頭から $5$ 番目の社員のアウトプット量は $A_4 = 2$ です。現在解雇されていない社員は $\{3, 4, 5, 6\}$ の $4$ 人なので、アウトプット量を昇順に並べると $\{2, 2, 3, 3\}$ です。この中央値は $3$ であり、$A_4 < 3$ なので、社員 $4$ は即座に解雇されます。
• 先頭から $6$ 番目の社員のアウトプット量は $A_6 = 3$ です。現在解雇されていない社員は $\{3, 5, 6\}$ の $3$ 人なので、アウトプット量を昇順に並べると $\{2, 3, 3\}$ です。この中央値は $3$ であり、$A_6 \geq 3$ なので、社員 $6$ は解雇されません。

よって、この並べ方の場合に解雇されるteamLove株式会社の社員数は $3$ 人です。

$6!$ 通りのすべての並べ方について解雇される社員数を計算することで、求める期待値は $\frac{8}{3}$ であることがわかります。

これを $\bmod \ 998244353$ で示した $665496238$ が答えとなります。

15
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

0

全社員が最高のアウトプット量の場合、どの社員も解雇されません。

786
1 2 2 3 2 2 3 2 3 2 2 2 2 3 2 3 2 2 2 2 2 2 3 2 2 2 2 3 3 2 2 3 2 2 3 2 2 2 3 2 3 2 3 3 3 2 3 2 2 3 3 2 2 2 2 2 3 3 2 3 2 2 2 3 2 2 2 2 3 2 2 2 3 3 2 2 2 2 2 2 2 3 2 3 2 2 2 3 2 2 2 3 3 2 2 3 2 3 2 2 2 2 2 3 3 2 2 2 3 3 3 2 2 2 2 3 2 3 2 3 3 2 2 2 3 2 3 3 2 2 2 2 2 2 3 2 3 2 3 2 3 2 3 2 2 2 2 3 2 3 2 2 3 3 3 2 2 2 3 2 2 2 2 2 2 3 2 3 2 2 3 2 2 3 2 2 2 3 2 2 2 2 3 2 3 2 2 3 3 3 2 2 2 3 2 2 2 2 2 2 3 2 2 3 2 3 3 2 3 2 3 3 2 2 2 2 2 2 2 3 2 2 2 3 3 3 3 2 3 2 2 2 3 2 3 3 2 3 2 2 3 3 3 2 2 2 2 2 3 2 2 2 2 2 2 3 2 2 2 2 2 2 2 3 2 3 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 3 2 2 3 2 3 2 2 3 3 2 2 2 3 2 2 3 2 2 3 2 2 2 3 2 2 3 3 2 3 2 2 2 3 3 3 2 2 3 2 2 2 2 3 2 2 2 3 2 3 3 3 3 2 2 2 2 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2 3 2 2 2 2 2 2 2 3 2 3 3 2 3 2 2 3 2 2 2 2 2 2 3 2 3 2 2 2 3 2 2 2 2 2 2 3 2 2 3 3 2 3 2 2 2 3 2 3 3 3 2 2 2 3 2 2 2 3 2 2 3 2 2 2 3 3 2 2 3 2 2 2 2 2 2 3 2 3 2 2 2 2 2 3 3 2 2 2 2 3 2 2 3 3 2 3 2 2 2 2 2 2 2 2 2 2 3 2 3 3 2 2 2 2 2 2 2 3 2 3 2 2 2 2 2 2 2 3 3 2 2 2 3 3 2 2 3 3 2 2 3 2 2 2 3 3 2 3 2 2 2 2 2 2 2 2 2 2 3 2 2 2 3 2 2 2 2 2 2 2 3 2 2 2 2 2 3 2 2 2 2 3 3 2 3 3 2 2 2 2 2 3 3 2 3 2 3 3 3 2 3 3 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 2 2 2 2 2 2 3 2 3 2 2 2 2 2 3 2 3 2 2 2 3 2 2 2 3 2 2 3 3 2 2 3 2 2 3 2 2 2 3 3 2 2 2 2 2 2 2 2 3 2 3 2 3 2 2 2 3 3 3 2 3 2 2 2 3 2 2 2 2 2 3 3 2 2 2 3 2 3 2 2 2 2 2 2 2 2 2 2 2 2 3 2 2 3 2 2 2 3 2 2 2 2 2 2 2 2 2 2 2 3 2 2 3 2 2 3 2 2 2 3 2 2 2 3 3 2 2 3 2 2 2 3 3 2 2 2 2 3 2 2 2 2 3 2 2 2 2 3 2 3 3 2 3 2 3 2 2 2 3 2 3 3 3 3 2 2 2 2 3 3 2 2 3 3 2 2 2 3 3 2 3 2 3 2 2 2 2 2 2 2 3 2 2 2 2 3 2 2 2 3 2 2 2 3 2 2 2 2 2

1

$1$ 人だけアウトプット量が要求に満たなかったようです。残念ですが、teamLove株式会社の他の社員はこの $1$ 人とさよならしなければなりません。