Serein 拥有一间自己的实验室,在这里有 n 台主机,每个主机有一个编号 a_i(可以相同)。规定相连在一起的主机集合称为网络,且一个网络里的主机编号必须互不相同。特别地,一台主机也可称为网络。如果两台主机的编号间隔为 1,则这两台主机可以连在一起。如果有一台主机可以与若干台主机相连,则该主机一定会选择其中一个进行相连。按照上述规则,可以把主机划分到若干个网络里,使得每台主机在且仅在一个网络内。一个网络里的主机个数称为该网络的容量。对于所有主机相连方案,你需要找到一种方案,使得网络容量的最小值最小化,并输出最小容量。
输入
第一行一个整数 n (1 \leq n \leq 10^5) 代表主机个数。
第二行输入 n 个整数 a_i(0 \leq a_i \leq 10^9),代表第 i (1 \leq i \leq n) 个主机编号为 a_i 。
输出
输出一个整数,代表在实验室中的最小网络容量。
样例
标准输入 复制文本 |
6 1 2 1 2 1 2 |
标准输出 复制文本 |
2 |