No.99 ジャンピング駒
LayCurse問題文最終更新日: 2017-06-25 01:02:46
問題文
一次元の数直線上の整数座標に駒が $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$ 個の駒を消滅させることができます．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。