Cards

Seunghyun has $n$ cards, each with a front and a back. The front of each card holds one integer between $1$ and $2222$, and no two cards hold the same number. The back of each card has a picture of an animal, and no two cards have the same picture.

These are cards that could appear. The left picture is the front and the right picture is the back.

Seunghyun lays the cards on the floor in a row with the backs facing up and numbers them $1$ through $n$ in order. Let $c_i$ be the number on the front of card $i$. Seunghyun repeats the following until exactly one card is left on the floor.

1. He picks any two different cards he likes and turns them over so the fronts face up.
2. He puts the card with the smaller number into his pocket and lays the card with the larger number back on the floor with the back facing up.
3. If two or more cards are left on the floor, he goes back to step 1. If exactly one card is left, he takes every card out of his pocket and adds up the numbers on their fronts.

The animal pictures differ, so Seunghyun can tell the cards apart and can turn over exactly the two cards he wants every time. He likes big numbers, so he wants the final sum in his pocket to be as large as possible. Find that maximum sum.

The first line holds a natural number $n$, the number of cards. ($1 \le n \le 2222$)

The second line holds $c_1, c_2, \dots, c_n$ in order, separated by spaces. Each $c_i$ is an integer between $1$ and $2222$, and they are all different.

Print the largest possible sum on the first line.

In the first example only one play is possible. Seunghyun turns over the card with $3$ and the card with $4$, and after the card with $3$ goes into his pocket only one card is left on the floor, so the answer is $3$.

In the second example three plays are possible.

• He turns over the cards with $1$ and $3$, then the cards with $3$ and $5$, so the sum is $1 + 3 = 4$.
• He turns over the cards with $1$ and $5$, then the cards with $3$ and $5$, so the sum is $1 + 3 = 4$.
• He turns over the cards with $3$ and $5$, then the cards with $1$ and $5$, so the sum is $3 + 1 = 4$.

The answer is therefore $4$.