← 返回题目列表

Codeforces · 649/D

D. 内存碎片整理

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

计算机内存由 n 个单元组成,这些单元排成一行。让我们从左到右将单元格编号为 1 到 n。对于每个单元,都知道它是空闲的还是属于某个进程(在这种情况下,它所属的进程是已知的)。

对于每个进程,已知属于它的单元占据内存中的连续区域。使用“将数据从占用的单元重写为空闲的单元,并且现在认为占用的单元是空闲的”形式的操作,有必要在计算机内存的开头找到属于进程的所有单元。换句话说,任何空闲单元必须位于任何已占用单元的右侧(具有更高的编号)。

您需要找到将数据从一个单元格重写到另一个单元格的最少操作次数,借助它您可以实现所描述的条件。每个进程的内存单元的相对顺序在碎片整理后发生变化是可以接受的,但进程本身的相对顺序应该保持不变。这意味着,如果属于进程 i 的所有单元先于进程 j 的所有单元进入内存,则即使在移动之后也必须满足此条件。

假设所有进程的编号都是唯一的,至少有一个内存单元被某个进程占用。

输入

输入的第一行包含数字 n (1 ≤ n ≤ 200 000) — 计算机内存中的单元数。

输入的第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ n),其中 ai 为 0(这意味着第 i 个存储单元空闲)或拥有第 i 个存储单元的进程号。保证ai至少有一个值不等于0。

进程按随机顺序用 1 到 n 的整数进行编号。在这种情况下,进程不必按顺序编号。

输出

打印一个整数 — 对内存进行碎片整理所需执行的最少操作数。

示例

输入 #1

4
0 2 2 1

输出 #1

2

输入 #2

8
0 8 8 8 0 4 4 2

输出 #2

4

注意

在第一个测试示例中,两个操作就足够了:

1. 将数据从第三个单元格复制到第一个单元格。之后,计算机内存将如下所示:2 2 0 1。
2. 将数据从第四个单元格复制到第三个单元格。此后,计算机内存将采用以下形式:2 2 1 0。