Maximum Pairs of Books with Different Genres

You are given n books, each book belongs to a certain genre represented by an integer. Your task is to determine the maximum number of pairs of books with different genres that can be formed.

Formally, given an integer \( n \) and a sequence \( genres = [g_1, g_2, \dots, g_n] \), you need to find the maximum number of pairs \( (i,j) \) such that \( g_i \neq g_j \) and each book is used at most once.

A useful observation is that the maximum number of such pairs is given by \[ \min\left(\left\lfloor \frac{n}{2} \right\rfloor,\; n - \max_{g}\;\text{count}(g)\right), \] where \( \max_{g}\;\text{count}(g) \) is the highest frequency of any genre in the list.

inputFormat

The input is read from stdin and consists of two lines.

• The first line contains a single integer \( n \) representing the total number of books.
• The second line contains \( n \) integers separated by spaces, where each integer represents the genre of a book.

outputFormat

Output a single integer to stdout representing the maximum number of pairs of books with different genres that can be formed.

## sample

6
1 2 3 1 2 3

3

</p>