No.1285 Garbage Disposal
Problem Statement
Piddy's room contains empty instant noodle cups of $N$ kinds, $1$ of each, and the container size of the $i$-th empty cup is $A_i$.
Piddy is going to throw away these $N$ items, but since throwing them away separately is space-inefficient,
he wants to stack the containers as much as possible when throwing them away.
For distinct integers $i,\ j$, containers $i,\ j$ can be stacked and thrown away
if and only if $A_i + 1 < A_j$ holds. (It is also possible to stack $3$ or more containers.)
What is the minimum possible number of groups of containers to throw away?
Input
$N$ $A_1$ $A_2$ $\dots$ $A_N$
- $1 \le N \le 10^5$
- $1 \le A_i \le 10^9\ (1 \le i \le N)$
- $A_i \neq A_j\ (1 \le i < j \le N)$
- All inputs are given as integers.
Output
Output the answer on $1$ line, followed by a newline.
Sample
Sample 1
Input
3 14 15 9
Output
2
Container $1$ and container $2$ cannot be stacked, but container $3$ can be stacked with either container $1$ or container $2$, only one of them. Therefore, the answer is $2$.
Sample 2
Input
2 7 18
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
piddy
kya_ski