According to the PWN dictionary, a "leader" is, among other things, "a leader of a political party, trade union, or other social organization." In algorithmics, however, a leader of a sequence of elements is an element whose number of occurrences is strictly greater than half the length of the sequence. For example, the leader of the sequence $[7, 2, 5, 7, 7]$ is the number $7$, while the sequence $[2, 3, 2, 3]$ has no leader at all.

In this task, we focus on the second meaning of the word "leader." Given a sequence of numbers, your task is to partition it into the minimum number of subsequences (not necessarily contiguous), each of which has a leader, and output this minimum number. It can be shown that such a partition is always possible.

Input

The first line of input contains a single integer $n$ ($1 \le n \le 500\,000$), representing the length of the sequence.

The second line of input contains a sequence of $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Output

The only line of output should contain a single integer representing the minimum possible number of subsequences into which the input sequence can be partitioned such that each resulting subsequence has a leader.

Examples

Input 1

5
1 2 3 1 2

Output 1

2

Note 1

The input sequence can be partitioned, for example, into the subsequences $[1, 3, 1]$ and $[2, 2]$. In this way, both resulting subsequences will have a leader (the numbers $1$ and $2$, respectively).