Maximum Groups of Candies

You are given a list of candies, where each candy is represented by a string indicating its type. Your task is to form as many groups as possible where each group consists of exactly two candies of different types. In other words, if you form a pair, the two candies in that pair must have distinct types.

Input Constraints: The first line contains an integer \(n\) (\(1 \le n \le 10^5\)) indicating the total number of candies. The second line contains \(n\) space-separated strings, each representing a candy type.

Output: Output a single integer, which is the maximum number of valid groups (pairs) that can be formed. Each candy may be used in at most one group.

Hint: One useful observation is that if \(T\) is the total number of candies and \(M\) is the maximum frequency of any single type, then the answer is \(\min(\lfloor T/2 \rfloor, T-M)\). Use this formula to guide your solution.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

1. The first line contains a single integer (n), the number of candies.
2. The second line contains (n) space-separated strings, where each string denotes the type of a candy.

outputFormat

Output a single integer to standard output (stdout) representing the maximum number of groups (pairs) of candies that can be formed such that each group contains two candies of different types.## sample

6
choco mint berry choco mint berry

3