2023 蓝桥杯热身赛

Problem P10. 破解序列锁(15 分)

大事不妙!回文质数真的成为了科学界的一个伟大的概念,然而由于回文质数计算器性能太好,一伙劫匪闯入 Tom 和 Jerry 的家中抢走了计算器, Tom 在反抗过程中受伤,也被劫匪绑架当作人质,虎口脱险的 Jerry 必须尽快营救 Tom 。

Jerry 发动汽车时,却发现车被狡猾的劫匪锁住了, Jerry 用了三秒钟研究了一下这个锁,就立刻知道如何将其打开。这个锁是一个长度为 n 的序列, 序列最多只包含三种数字 ,分别是 -214748364802147483647 ,只有序列排成非降序时,锁才能打开。 Jerry 每次操作可以将序列中的 任意 两个数进行交换,留给 Jerry 的时间不多了,请问他破解锁最少需要多少次操作?

输入

第一行包含一个整数 n ,其中 1\leq n\leq 1000

接下来 n 行,每行包含一个整数,每个整数只可能是 -214748364802147483647 的其中一个。

输出

输出包含一个整数,表示将序列排成升序的最少操作次数。

样例

标准输入 复制文本
9
0
0
-2147483648
2147483647
2147483647
2147483647
0
2147483647
-2147483648
标准输出 复制文本
4

提示

对于 10 分的数据, n\leq 100

对于 15 分的数据, n \leq 1000

登录以提交代码。
单点时限 2 秒
内存限制 128 MB
提交 15
通过 8