题目描述

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

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

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

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

输入格式

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

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

输出格式

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

题目大意

给定一个长度为 $N$ 的序列 $A=(A_1, A_2, ..., A_N)$，其中每个元素都是介于 $1$ 和 $4$ 之间的整数。

可以进行以下操作任意次（可能为零次）：

• 选择一对整数 $(i, j)$，其中 $1≤i<j≤N$，并交换 $A_i$ 和 $A_j$。

输出使序列 $A$ 变为非递减序列所需的最小操作次数。

非递减序列是指对于所有 $1≤i≤N−1$，都满足 $A_i≤A_{i+1}$ 的序列。

6
3 4 1 1 2 4

3

4
2 3 4 1

3

提示

制約

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

Sample Explanation 1

次のようにして $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$ を出力します。