Liderzy

The word lider (translated from Polish) originally means a leader of a political party, union, or other social organization. In algorithms, however, we call an element a leader of a sequence if it occurs in the sequence strictly more than half of the total number of elements. For example, the sequence \( [7,2,5,7,7] \) has leader \( 7 \) because \( 7 \) appears 3 times (and \(3 > 5/2\)), while the sequence \( [2,3,2,3] \) has no leader.

In this problem we consider the algorithmic meaning. You are given a sequence of integers. Your task is to partition this sequence (by selecting subsequences – the elements in one group do not need to be consecutive in the original sequence) into a minimum number of parts so that every part has a leader. It can be proved that such a partition always exists.

A subsequence with leader \( x \) is defined as a nonempty group of numbers where the number of occurrences of \( x \) is strictly greater than half of the size of the subsequence. Equivalently, if a subsequence has size \( L \) and contains \( r \) copies of \( x \), then \( r > L/2 \) (or, equivalently, \( L \le 2r-1 \)).

The challenge is to determine and output the minimum number of subsequences required. For instance, consider the following examples:

• For the sequence [7, 2, 5, 7, 7] (with \( n = 5 \) and the leader candidate \( 7 \) appearing \( 3 \) times), the entire sequence itself has a leader since \( 5 \le 2\times3-1=5 \). Thus, the answer is 1.
• For the sequence [2, 3, 2, 3] (with \( n = 4 \) and the maximum frequency any number appears is \( 2 \)), no single group of size 4 has a leader because \( 2 \) is not strictly more than \( 4/2=2 \). One valid partition is \( [2,3,2] \) and \( [3] \); therefore, the answer is 2.

A useful observation in solving the problem is as follows. Let \( n \) be the length of the sequence and let \( m \) be the maximum frequency among all values in the sequence. Note that if \( n \le 2m-1 \) then all elements can be put in one group with the value that appears \( m \) times acting as the leader. Otherwise, in the worst‐case scenario (for example, when all the other \( n-m \) elements are distinct), one optimal strategy is to take one group formed by using all \( m \) occurrences of the popular element (which can cover at most \( 2m-1 \) numbers) and then to put every leftover element in its own group. Hence, the minimum number of groups required is given by:

[ \text{answer} = \begin{cases} 1, & \text{if } n \le 2m-1,\ n - 2m + 2, & \text{if } n > 2m-1. \end{cases} ]

Implement a program that computes this minimum number.

inputFormat

The first line of input contains a single integer \( n \) (\( 1 \le n \le 10^5 \)) denoting the number of elements in the sequence.

The second line contains \( n \) integers \( a_1, a_2, \ldots, a_n \) (\( 1 \le a_i \le 10^9 \)) representing the sequence.

outputFormat

Output a single integer, the minimum number of subsequences into which the sequence can be partitioned so that every subsequence has a leader.

sample

5
7 2 5 7 7

1