← 返回题目列表

AtCoder · abc302_g

G. 从 1 到 4 排序

中文机器翻译题面 查看原题

分数: 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