問題一覧 > 通常問題

No.1285 ゴミ捨て

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 207
作問者 : piddypiddy / テスター : kya_skikya_ski
13 ProblemId : 5376 / 出題時の順位表
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。