AT_abc302_g [ABC302G] Sort from 1 to 4

题目描述

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

高桥君可以进行如下操作任意多次（也可以不进行）：

• 选择满足 $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$ 变为广义单调递增所需的最小操作次数。

输入输出样例 #1

输入 #1

6
3 4 1 1 2 4

输出 #1

3

输入输出样例 #2

输入 #2

4
2 3 4 1

输出 #2

3

说明/提示

限制条件

• $2 \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq 4$
• 输入均为整数

样例解释 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 次或更少的操作完成，因此最小操作次数为 3。输出 3。

由 ChatGPT 4.1 翻译