Magical Palindromic Sequence

You are given an integer n and an array of n integers. Your task is to determine the maximum length of a Magical Palindromic Sequence that can be constructed using some or all of the integers from the array.

A palindromic sequence is one that reads the same forwards and backwards. Formally, for each integer with frequency \( f \) in the array, you can use \( 2\lfloor f/2 \rfloor \) of them in the sequence, and if there is at least one integer with an odd frequency, you may place one additional integer in the center. That is, the answer is given by:

\( \text{length} = \sum_{i=1}^{m} 2\left\lfloor \frac{f_i}{2} \right\rfloor + \mathbb{I}\Big(\exists\, i: f_i \text{ mod } 2 = 1\Big) \)

Help Chef find this maximum length.

inputFormat

The first line contains an integer n representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output a single integer denoting the maximum length of the Magical Palindromic Sequence that can be formed from the given array.

6
1 2 3 2 3 1

6