← 返回题目列表

AtCoder · awc0019_c

C. 连续发卡

中文机器翻译题面 查看原题

分数: 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