分数: 625 点
问题陈述
给你一个序列 A=(A_1,A_2,\ldots,A_N) 长度 N,由之间的整数组成 1 和 4.
Takahashi 可以执行以下操作任意次数(可能为零):
- 选择一对整数 (i,j) 这样 1\leq i<j\leq N,并交换 A_i 和 A_j.
找出完成该操作所需的最少操作数 A 非减少。
序列称为非减序列当且仅当 A_i\leq A_{i+1} 对于所有人 1\leq i\leq N-1.
约束
- 2 \leq N \leq 2\times 10^5
- 1\leq A_i \leq 4
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印完成所需的最少操作数 A 单行非递减。
样本输入 1
6 3 4 1 1 2 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).
这是最少的操作次数,因为不可能使 A 两次或更少操作时非递减。
因此, 3 。
示例输入 2
4 2 3 4 1
示例输出 2
3