分数: 300 分
问题陈述
高桥正在组织一场纸牌游戏锦标赛。
比赛使用 N 卡。卡 i (1 \leq i \leq N) 有一个正整数 上面写着 A_i ,所有整数都写在上面 N 卡片是不同的。
高桥想要瓜分所有 N 卡片分为几组。每张卡必须恰好属于一个组,并且每个组必须至少包含一张卡。此外,每个组必须是如下定义的“连续组”。
一套卡片是 连续组 如果其中卡片上写的整数集合可以表示为 \{a, a+1, a+2, \ldots, a+k-1\} 对于某个整数 a 和正整数 k。换句话说,它是一个由以下组成的集合 k 连续整数。当 k = 1,即仅由一张牌组成的组,它也是一个连续的组。
例如,一组 3 带有整数的卡片 写在上面的 3, 5, 4 形成整数集 \{3, 4, 5\},其中包括 3 连续的整数,所以它是一个连续的组。另一方面,一组 3 带有整数的卡片 写在上面的 2, 4, 5 不是连续组,因为 3 之间缺少 2 和 4.
分割全部时 N 将卡片分成连续的组,求最少的组数。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- A_i \neq A_j (i \neq j)
- 所有输入均为整数
输入
N A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表卡片数量。
- 第二行包含正整数 每张卡片上写有 A_1, A_2, \ldots, A_N ,并用空格分隔。
输出
在一行中打印划分所有组时的最小组数 N 卡片分成连续的组。
示例输入 1
3 3 5 4
示例输出 1
1
示例输入 2
7 2 4 5 10 11 12 7
示例输出 2
4
示例输入 3
15 100 3 50 51 52 1 2 200 201 202 203 53 4 5 999999999
示例输出 3
5