题目描述

给定长度为 $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$。

5
1 0 4 1 0

2

6
1 1 4 5 1 4

0

7
1 9 1 9 8 1 0

1

8
1 3 8 0 0 98 40 138

2

提示

【样例解释 #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$。