No.1285 ゴミ捨て
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 280
作問者 :
piddy
/ テスター :
kya_ski
タグ : / 解いたユーザー数 280
作問者 :
piddy
/ テスター :
kya_ski
問題文最終更新日: 2020-10-15 20:26:24
問題文
piddy くんの部屋にはカップ麺の食べガラ $N$ 種類が $1$ 個ずつあり、$i$ 個目の食べガラの容器の大きさは $A_i$ です。
piddy くんはこれら $N$ 個を捨てようとしていますが、バラバラに捨てるのは空間効率が悪いので、
容器をできるだけ重ねて捨てたいです。
異なる整数 $i,\ j$ に対し $A_i + 1 < A_j$ が成り立つとき、またそのときに限り
容器 $i,\ j$ は重ねて捨てることができます。( $3$ 個以上重ねることも可能です。)
捨てる容器のまとまりは最小で何個になりますか？
入力
$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)$
- 入力は全て整数で与えられる。
出力
答えを $1$ 行に出力し、最後に改行してください。
サンプル
サンプル1
入力
3 14 15 9
出力
2
容器 $1$ と容器 $2$ は重ねることができませんが、容器 $3$ は容器 $1$ または容器 $2$ の いずれか一方と重ねることができます。よって答えは $2$ です。
サンプル2
入力
2 7 18
出力
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。