問題文

$N$ 枚のカードが一列に並べられており、左から $i$ 番目のカードは数として $A_i$ が書かれています。

あなたは、以下の操作を何回でも行うことができます。

• 同じ数が書かれたカードを $2$ 枚選び、そのカードを消去する。

あなたが行える操作回数の最大値を求めてください。

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq N$
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$A_1$ $A_2$ ... $A_{N}$ 

出力

問題の答えを一行に出力せよ。

サンプル

5
1 2 3 1 2

2

10
1 2 3 4 5 6 7 8 9 8

1