No.99 ジャンピング駒

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 362
作問者 : LayCurseLayCurse
3 ProblemId : 191 / 出題時の順位表

問題文

一次元の数直線上の整数座標に駒が $N$ 個あります.
各駒の初期座標は互いに異なり $X_1,X_2,\ldots,X_N$ です.
$1$ 回の操作では $1$ 個の駒を動かすことができ,今いる座標が $x$ ならば $x+2$ または $x-2$ に移動できます.
ただし,移動先に既に駒がある場合はそのような移動はできず,また,移動するにあたって,駒を飛び越えた場合は,飛び越えた駒と飛び越えられた駒の両方が消滅します.
駒の数を最小化したいです.
操作は何回でもできるとして,最後まで残る駒の個数の最小値を求めるプログラムを書いて下さい.

入力

$N$
$X_1$ $X_2$ $\cdots$ $X_N$

$1 \leq N \leq 10^5$
$-10^9 \leq X_k \leq 10^9$

出力

残る駒の個数の最小値を $1$ 行で出力して下さい.
最後に改行してください.

サンプル

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

座標 $2$ にいる駒が座標 $1$ にいる駒を飛び越え,その後,座標 $4$ にいる駒が座標 $3$ にいる駒を飛び越えれば全ての駒が消滅します.

サンプル2
入力
10
-746 0 11 98 1 14 998 123 837 15
出力
0

なんかうまくやれば全部消滅するらしいです.

サンプル3
入力
5
1000000000 -1000000000 0 987654321 -123456789
出力
1

駒が消滅するときは $2$ 個セットで消滅するので,最後にどうしても $1$ 個の駒は残ってしまいます.
また,$4$ 個の駒を消滅させることができます.

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

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