/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君はカードゲームの大会を運営しています。
大会には N 枚のカードが使用されます。カード i（1 \leq i \leq N）には正の整数 A_i が書かれており、N 枚のカードに書かれた整数はすべて異なります。
高橋君は、これらの N 枚のカードすべてをいくつかのグループに分けたいと考えています。ただし、各カードはちょうど 1 つのグループに属さなければならず、どのグループにも 1 枚以上のカードが含まれていなければなりません。さらに、各グループは以下で定義される「連番グループ」でなければなりません。
あるカードの集合が連番グループであるとは、そこに含まれるカードに書かれた整数を集めた集合が、ある整数 a と正の整数 k を用いて \{a, a+1, a+2, \ldots, a+k-1\} と表せることを指します。すなわち、連続する k 個の整数からなる集合です。k = 1 の場合、すなわちカード 1 枚だけからなるグループも連番グループです。
例えば、書かれた整数が 3, 5, 4 である 3 枚のカードの集合は、整数の集合として \{3, 4, 5\} となり連続する 3 個の整数からなるので連番グループです。一方、書かれた整数が 2, 4, 5 である 3 枚のカードの集合は、2 と 4 の間に 3 が欠けているため連番グループではありません。
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
- 1 行目には、カードの枚数を表す整数 N が与えられる。
- 2 行目には、各カードに書かれた正の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
出力
N 枚のカードすべてを連番グループに分けるときの、グループ数の最小値を 1 行で出力せよ。
入力例 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
Score : 300 pts
Problem Statement
Takahashi is organizing a card game tournament.
The tournament uses N cards. Card i (1 \leq i \leq N) has a positive integer A_i written on it, and all integers written on the N cards are distinct.
Takahashi wants to divide all N cards into several groups. Each card must belong to exactly one group, and every group must contain at least one card. Furthermore, each group must be a "consecutive group" as defined below.
A set of cards is a consecutive group if the set of integers written on the cards in it can be expressed as \{a, a+1, a+2, \ldots, a+k-1\} for some integer a and positive integer k. In other words, it is a set consisting of k consecutive integers. When k = 1, i.e., a group consisting of just one card, it is also a consecutive group.
For example, a set of 3 cards with the integers 3, 5, 4 written on them forms the integer set \{3, 4, 5\}, which consists of 3 consecutive integers, so it is a consecutive group. On the other hand, a set of 3 cards with the integers 2, 4, 5 is not a consecutive group because 3 is missing between 2 and 4.
When dividing all N cards into consecutive groups, find the minimum number of groups.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- A_i \neq A_j (i \neq j)
- All inputs are integers
Input
N A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of cards.
- The second line contains the positive integers A_1, A_2, \ldots, A_N written on each card, separated by spaces.
Output
Print in one line the minimum number of groups when dividing all N cards into consecutive groups.
Sample Input 1
3 3 5 4
Sample Output 1
1
Sample Input 2
7 2 4 5 10 11 12 7
Sample Output 2
4
Sample Input 3
15 100 3 50 51 52 1 2 200 201 202 203 53 4 5 999999999
Sample Output 3
5