Maximize Beautiful Pairs

You are given a sequence of n integers. Your task is to determine the maximum number of beautiful pairs that can be obtained after rearranging the sequence such that no two adjacent elements are the same.

A beautiful pair is defined as any adjacent pair of numbers in the rearranged sequence where the two numbers are distinct. For a valid rearrangement in which no two identical numbers are adjacent, the maximum number of beautiful pairs is n - 1. If it is impossible to rearrange the sequence to satisfy this condition, output -1.

The condition to check for a valid rearrangement is based on the maximum frequency of any element in the array. Specifically, if the maximum frequency is greater than \( \left\lceil \frac{n}{2} \right\rceil \), then it is impossible to rearrange the sequence without having two equal elements adjacent.

Input Format: The first line contains an integer n representing the number of elements. The second line contains n space-separated integers.

Output Format: Print a single integer representing the maximum number of beautiful pairs (which is n - 1) if a valid rearrangement exists; otherwise, print -1.

inputFormat

The input is read from standard input. It consists of:

1. An integer n on the first line, representing the number of elements in the array.
2. The second line contains n space-separated integers.

outputFormat

Output a single integer to standard output: n - 1 if a valid rearrangement exists, otherwise -1.

5
1 2 2 3 3

4