根據 PWN 字典，「領袖」（lider）是指「政黨、工會或其他社會組織的領導者」。而在演算法中，我們將數列的領袖定義為出現次數嚴格大於數列長度一半的元素。例如，數列 $[7, 2, 5, 7, 7]$ 的領袖是 $7$，而數列 $[2, 3, 2, 3]$ 則完全沒有領袖。

在本題中，我們將專注於「領袖」的第二種定義。給定一個數列，你的任務是將其劃分為最少數量的子數列（不一定要連續），使得每個子數列都擁有領袖，並輸出這個最小數量。可以證明，這樣的劃分總是可能的。

輸入格式

第一行包含一個整數 $n$ ($1 \le n \le 500\,000$)，代表數列的長度。

第二行包含 $n$ 個整數 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。

輸出格式

輸出僅一行，包含一個整數，代表將輸入數列劃分為每個子數列皆擁有領袖的子數列時，所需的最少數量。

範例

輸入 1

5
1 2 3 1 2

輸出 1

2

說明 1

輸入數列可以劃分為例如 $[1, 3, 1]$ 和 $[2, 2]$。如此一來，兩個結果數列都擁有領袖（分別為 $1$ 和 $2$）。