Maximum Palindromic Segment Sum

You are given a shelf with n books, where the i-th book has a thickness given by an integer. Your task is to rearrange the books in any order to form a contiguous segment (subarray) that is a palindrome, while maximizing the sum of the thicknesses of the chosen segment.

A palindrome is a sequence that reads the same backward as forward. Note that you may use all or some of the books and you are allowed to rearrange the books optimally to form such a segment.

---

Input: The first line contains an integer n representing the number of books. The second line contains n integers, where the i-th integer represents the thickness of the i-th book.

Output: Print a single integer which is the maximum possible sum of the book thicknesses in any contiguous palindrome segment that can be formed by an optimal rearrangement.

Note: It is optimal to pair up books of the same thickness to contribute twice to the sum and if available, one unpaired book (with the maximum thickness among the leftovers) can be placed in the middle. Mathematically, if you have a thickness with frequency f, you contribute 2 \cdot thickness \cdot \lfloor f/2 \rfloor from that thickness and you can add the maximum thickness among the ones with odd frequency.

The mathematical formulation of the summing process involving frequencies and pairing is given by:

$$\text{answer} = \sum_{\text{thickness}\; t}\, t \cdot (2 \lfloor f(t)/2 \rfloor) + \max_{t\, :\, f(t) \% 2 = 1}\{t\}$$

inputFormat

The input is given in two lines:

• The first line contains a single integer n — the number of books.
• The second line contains n space-separated integers, where each integer denotes the thickness of a book.

You can assume that 1 \leq n \leq 10^5 and the thicknesses are positive integers.

outputFormat

Output a single integer — the maximum possible sum of the thicknesses in any contiguous palindrome segment formed by optimally rearranging the books.

## sample

5
1 4 1 4 1

11