카드

승현이는 앞면과 뒷면이 있는 카드 $n$장을 가지고 있습니다. 각 카드의 앞면에는 $1$ 이상 $2222$ 이하의 정수가 하나씩 적혀 있고, 이 수는 카드마다 서로 다릅니다. 각 카드의 뒷면에는 동물 그림이 그려져 있으며, 이 그림도 카드마다 서로 다릅니다.

가능한 카드의 예시입니다. 왼쪽 그림이 앞면, 오른쪽 그림이 뒷면입니다.

승현이는 카드를 뒷면이 보이도록 바닥에 일렬로 늘어놓고, 차례대로 $1$번부터 $n$번까지 번호를 붙였습니다. $i$번 카드의 앞면에 적힌 수를 $c_i$라고 합시다. 승현이는 바닥에 카드가 정확히 한 장 남을 때까지 다음 행동을 반복합니다.

1. 마음에 드는 서로 다른 카드 두 장을 앞면이 보이도록 뒤집어 봅니다.
2. 앞면에 더 작은 수가 적힌 카드를 주머니에 넣고, 더 큰 수가 적힌 카드는 다시 뒷면이 보이도록 바닥에 내려놓습니다.
3. 바닥에 카드가 두 장 이상 남았다면 1번으로 돌아갑니다. 정확히 한 장 남았다면 주머니에 든 카드를 모두 꺼내 앞면에 적힌 수의 합을 구합니다.

뒷면의 동물 그림이 서로 다르므로 승현이는 어느 카드가 어느 카드인지 구별할 수 있고, 매번 원하는 두 장을 정확히 골라 뒤집을 수 있습니다. 승현이는 큰 수를 좋아해서 마지막에 주머니에 든 수의 합을 가능한 한 크게 만들려고 합니다. 그 합의 최댓값을 구해 주세요.

첫 번째 줄에 카드의 수를 나타내는 자연수 $n$이 주어집니다. ($1 \le n \le 2222$)

두 번째 줄에 $c_1, c_2, \dots, c_n$이 공백을 사이에 두고 차례대로 주어집니다. 각 $c_i$는 $1$ 이상 $2222$ 이하의 정수이고, 서로 다릅니다.

첫 번째 줄에 가능한 최대 합을 출력합니다.

첫 번째 예제에서 가능한 경우는 한 가지뿐입니다. 승현이는 $3$이 적힌 카드와 $4$가 적힌 카드를 뒤집게 되고, $3$이 적힌 카드를 주머니에 넣고 나면 바닥에 한 장만 남으므로 답은 $3$입니다.

두 번째 예제에서 가능한 경우는 세 가지입니다.

• 처음에 $1$이 적힌 카드와 $3$이 적힌 카드를 뒤집고, 다음에 $3$이 적힌 카드와 $5$가 적힌 카드를 뒤집으면 합은 $1 + 3 = 4$입니다.
• 처음에 $1$이 적힌 카드와 $5$가 적힌 카드를 뒤집고, 다음에 $3$이 적힌 카드와 $5$가 적힌 카드를 뒤집으면 합은 $1 + 3 = 4$입니다.
• 처음에 $3$이 적힌 카드와 $5$가 적힌 카드를 뒤집고, 다음에 $1$이 적힌 카드와 $5$가 적힌 카드를 뒤집으면 합은 $3 + 1 = 4$입니다.

따라서 답은 $4$입니다.