No.921 ずんだアロー

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 149
作問者 : Lemma299Lemma299 / テスター : lumc_lumc_
1 ProblemId : 3394 / 出題時の順位表

数式が表示されない不具合が発生している場合は次の対応をお願いします.

https://twitter.com/yukicoder/status/1191757446596812800?s=20

問題文

$N$ 個の餅が並んでいて,左から $i$ 番目の位置にある餅の大きさは $A_i$ です.
ずん子はずんだアローによって餅をずんだ餅に変化させることを好きな回数行えます.
また,ずんだ餅は餅と隣り合っているときにはなにも起きませんが,ずんだ餅と隣り合っているときは以下のように変化します.

  • 隣り合うずんだ餅が同じ大きさのときは変化しない.
  • 隣り合うずんだ餅が異なる大きさの場合,小さい方のずんだ餅が消滅する(大きい方のずんだ餅は変化しない).
この変化は大きさの異なるずんだ餅が隣り合わなくなるまで続きます(変化の順序によらず最終的な結果は一意に定まります).
ずん子がうまくずんだ餅に変化させる餅を選んだ時,最終的に残すことができるずんだ餅の最大個数を求めてください.

入力

$N$
$A_1\ A_2\ \cdots\ A_{N - 1}\ A_N$
  • $1 \le N \le 10^5$
  • $1 \le A_i \le 10^5$
  • 入力はすべて整数.

出力

最終的に残すことができるずんだ餅の最大個数を整数で一行に表示してください.

サンプル

サンプル1
入力
5
1 2 3 4 5
出力
3

左から 1, 3, 5 番目の餅をずんだ餅に変化させることで達成できます.

サンプル2
入力
9
1 2 2 2 1 3 2 2 2
出力
6

大きさが 2 の餅をすべてずんだ餅に変化させることで達成できます.
大きさが同じずんだ餅同士は吸収しないことに注意してください.

サンプル3
入力
8
7 1 6 8 9 4 3 2
出力
4

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。