PWN辞書によれば、「リーダー（lider）」とは「政党、労働組合、その他の社会組織の指導者」などを指します。一方、アルゴリズムの分野において、数列のリーダーとは、その出現回数が数列の長さの半分を厳密に上回る要素のことを指します。例えば、数列 $[7, 2, 5, 7, 7]$ のリーダーは $7$ ですが、数列 $[2, 3, 2, 3]$ にはリーダーが存在しません。

この問題では、後者の「リーダー」の意味に焦点を当てます。与えられた数列を、それぞれがリーダーを持つような最小個数の部分列（必ずしも連続である必要はありません）に分割し、その最小個数を出力してください。このような分割は常に可能であることが証明できます。

入力

入力は以下の形式で与えられます。

$n$ $a_1, a_2, \dots, a_n$

1行目には、数列の長さを表す整数 $n$ ($1 \le n \le 500\,000$) が与えられます。 2行目には、数列の各要素を表す $n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) が与えられます。

出力

与えられた数列を、それぞれがリーダーを持つような部分列に分割する際の、最小の分割数を出力してください。

入出力例

入力 1

5
1 2 3 1 2

出力 1

2

注記

例の解説：入力された数列は、例えば $[1, 3, 1]$ と $[2, 2]$ という2つの部分列に分割できます。このように分割することで、それぞれの部分列はリーダー（それぞれ $1$ と $2$）を持つことになります。