logo AlgoBeat OnlineJudge
登录 注册

#214168. 【MX-X22-T1】「TPOI-4A」MEX Problem

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

给定长度为 的非负整数序列

你需要将这个序列划分为尽可能多个子序列,使得:

  • 每个子序列至少包含一个元素;
  • 每个元素被划分进了恰好一个子序列;
  • 每个子序列的 都不为

设子序列个数为 ,你只需要求出满足条件的 的最大可能值。如果不存在满足条件的 ,输出

子序列的定义:从原序列中选取一部分元素,不改变它们在原序列中的相对顺序,得到的新序列。

非负整数序列的 的定义:该序列中没有出现过的最小非负整数。例如:

输入格式

第一行,一个正整数 ,表示序列长度。

第二行, 个非负整数

输出格式

输出一行,一个非负整数,表示 的最大可能值。如果不存在满足条件的 ,输出

样例

样例输入 1

5
1 0 4 1 0

样例输出 1

2

样例输入 2

6
1 1 4 5 1 4

样例输出 2

0

样例输入 3

7
1 9 1 9 8 1 0

样例输出 3

1

样例输入 4

8
1 3 8 0 0 98 40 138

样例输出 4

2

数据范围与提示

【样例解释 #1】

序列为

划分进第一个子序列, 划分进第二个子序列,此时:

  • 第一个子序列为
  • 第二个子序列为

该划分方案满足条件,且有

可以证明不存在划分为更多子序列的方案。

【数据范围】

测试点编号 特殊性质
A
^
  • 特殊性质 A:保证序列 不含

对于所有数据,保证