根据 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$）。