配点 : $625$ 点

問題文

全ての要素が $1$ 以上 $4$ 以下の整数である、長さ $N$ の数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。

高橋君は次の操作を何回でも ($0$ 回でも良い) 繰り返し行う事ができます。

• $1\leq i をみたす整数の組$(i,j)$を選び、$A_i$と$A_j$ を交換する。

数列 $A$ を広義単調増加にするために必要な操作回数の最小値を求めてください。 ただし、数列 $A$ が広義単調増加であるとは、$1\leq i\leq N-1$ をみたすすべての整数について $A_i\leq A_{i+1}$ が成り立つことをさします。

制約

• $2 \leq N \leq 2\times 10^5$
• $1\leq A_i \leq 4$
• 入力はすべて整数

入力

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

$N$

$A_1$ $A_2$ $\ldots$ $A_N$

出力

数列 $A$ を広義単調増加にするために必要な操作回数の最小値を一行に出力せよ。

6
3 4 1 1 2 4

3

次のようにして $3$ 回の操作で $A$ を広義単調増加にすることができます。

• $(i,j)=(2,3)$ を選び、$A_2$ と $A_3$ を交換する。$A=(3,1,4,1,2,4)$ となる。
• $(i,j)=(1,4)$ を選び、$A_1$ と $A_4$ を交換する。$A=(1,1,4,3,2,4)$ となる。
• $(i,j)=(3,5)$ を選び、$A_3$ と $A_5$ を交換する。$A=(1,1,2,3,4,4)$ となる。

$2$ 回以下の操作で $A$ を広義単調増加にすることはできないため、このとき操作回数が最小となります。 よって、$3$ を出力します。

4
2 3 4 1

3