P14130 【MX-X22-T1】「TPOI-4A」MEX Problem

给定长度为 $n$ 的非负整数序列 $a_1, \ldots, a_n$。 你需要将这个序列划分为尽可能多个**子序列**，使得： - 每个子序列至少包含一个元素； - 每个元素被划分进了恰好一个子序列； - 每个子序列的 $\operatorname*{mex}$ 都不为 $0$。 设子序列个数为 $k$，你只需要求出满足条件的 $k$ 的最大可能值。如果不存在满足条件的 $k$，输出 $0$。 **子序列的定义**：从原序列中选取一部分元素，不改变它们在原序列中的相对顺序，得到的新序列。 **非负整数序列的 $\textbf{mex}$ 的定义**：该序列中没有出现过的最小非负整数。例如： - $[1, 2, 1]$ 的 $\operatorname*{mex}$ 为 $0$； - $[3, 0, 4]$ 的 $\operatorname*{mex}$ 为 $1$； - $[7, 1, 0, 1]$ 的 $\operatorname*{mex}$ 为 $2$。

第一行，一个正整数 $n$，表示序列长度。 第二行，$n$ 个非负整数 $a_1, \ldots, a_n$。

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

**【样例解释 #1】** 序列为 $a = [1, 0, 4, 1, 0]$。 将 $a_1, a_4, a_5$ 划分进第一个子序列，$a_2, a_3$ 划分进第二个子序列，此时： - 第一个子序列为 $[1, 1, 0]$，$\operatorname*{mex}$ 为 $2$； - 第二个子序列为 $[0, 4]$，$\operatorname*{mex}$ 为 $1$。 该划分方案满足条件，且有 $k = 2$。 可以证明不存在划分为更多子序列的方案。 **【数据范围】** | 测试点编号 | $n \le$ | 特殊性质 | | :----------: | :----------: | :----------: | | $1,2$ | $10^5$ | A | | $3,4$ | $5$ | 无 | | $5\sim 10$ | $10^5$ | ^ | - 特殊性质 A：保证序列 $a$ 不含 $0$。 对于所有数据，保证 $1 \le n \le 10^5$，$0 \le a_i \le 10^9$。