从 1 到 4 排序

题目描述

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

高桥可以任意多次（也可以零次）执行以下操作：

选择一对整数 $(i,j)$，满足 $1 \le i \lt j \le N$，交换 $A_i$ 和 $A_j$。

求使 $A$ 变为非递减序列所需的最少操作次数。

若对于所有 $1 \le i \le N-1$ 都有 $A_i \le A_{i+1}$，则称该序列为非递减序列。

输入格式

输入按以下格式从标准输入给出：

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

输出格式

在一行中输出使 $A$ 变为非递减序列所需的最少操作次数。

样例

6
3 4 1 1 2 4

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)$。

因为用两次或更少的操作无法使 $A$ 变为非递减，所以这是最少的操作次数。

因此应输出 $3$。

4
2 3 4 1

3

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le A_i \le 4$
• 输入中的所有值均为整数。