← 返回题目列表

Codeforces · 886/C

C. 佩蒂亚和地下墓穴

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

一位非常勇敢的探险家 Petya 曾经决定探索巴黎地下墓穴。由于彼佳经验不足,他的探索只是在地下墓穴中行走。

地下墓穴由几个房间和一些房间之间的双向通道组成。有些通道可以将一个房间与其自身连接起来,并且由于通道建立在不同的深度上,因此它们不会彼此相交。每一分钟,Petya 都会从他当前所在的房间中任意选择一个通道,然后在整整一分钟内到达通道另一端的房间。当他在 i 分钟进入房间时,他在日志中记下编号 ti:

- 如果 Petya 以前访问过这个房间,他会写下他上次进入这个房间的时间;
- 否则,Petya 写下严格小于当前分钟 i 的任意非负整数。

最初,Petya 在 0 分钟时在其中一个房间,他没有写下数字 t0。

在他流浪的某个时刻,Petya 感到累了,扔掉了他的日志并回家了。瓦夏找到了他的航海日志,现在他很好奇:根据佩蒂亚的航海日志,巴黎地下墓穴的房间数量最少是多少?

输入

第一行包含一个整数 n (1 ≤ n ≤ 2·105) — 然后是 Petya 日志中的笔记数量。

第二行包含 n 个非负整数 t1, t2, ..., tn (0 ≤ ti < i) — 日志中的注释。

输出

在唯一的一行中打印一个整数——巴黎地下墓穴中可能的最小房间数。

示例

输入 #1

2
0 0

输出 #1

2

输入 #2

5
0 1 0 1 3

输出 #2

3

注意

在第一个样本中,Petya 访问的房间顺序可以是,例如 1 → 1 → 2、1 → 2 → 1 或 1 → 2 → 3。房间的最小可能数量为 2。

在第二个示例中,序列可能是 1 → 2 → 3 → 1 → 2 → 1。