카드 Batch Compilation commands

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

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

승현이는 카드들을 바닥에 뒷면이 보이도록 일렬로 늘어 놓고, 차례대로 1 이상 $n$ 이하의 자연수 번호를 붙였습니다. 이 중 $i$번 카드의 앞면에 적혀 있는 수를 $c_{i}$로 둡시다. 승현이는 바닥에 카드가 정확히 한 장 남을 때까지 아래와 같은 행동을 반복합니다.

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

승현이는 큰 수가 좋아서, 마지막에 주머니 속에 들어있는 카드들에 적혀 있는 수들의 합을 가능한 한 크게 하고자 합니다. (뒷면에 그려진 동물 그림이 서로 다르므로 방법만 알고 있다면 충분히 가능합니다!) 승현이를 도와주세요.

입력 형식

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

두 번째 줄에 $c_{1}, c_{2}, \cdots, c_{n}$이 공백을 사이에 두고 차례대로 주어집니다.

출력 형식

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

부분문제

부분문제	점수	$n$	추가 제약 사항
1	5	$n = 1$	-
2	15	$n = 2$	-
3	10	$n =$ $2,222$	-
4	25	$n \le$ $2,222$	모든 $1 \le i \le n$에 대하여 $c_{i} = i$
5	45	$n \le$ $2,222$	-

예제

입력

2
3 4

출력

3

이 예제에서 가능한 경우는 한 가지 뿐입니다.

승현이는 3이 적힌 카드와 4가 적힌 카드를 뽑게 되고, 3이 적힌 카드를 갖고 나면 남은 카드가 한 장밖에 없으므로 답은 3이 됩니다.

입력

3
1 3 5

출력

4

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

• 승현이가 처음에 1이 적힌 카드와 3이 적힌 카드를 뽑고, 다음에 3이 적힌 카드와 5가 적힌 카드를 뽑았을 경우 답은 1+3=4가 됩니다.
• 승현이가 처음에 1이 적힌 카드와 5가 적힌 카드를 뽑고, 다음에 3이 적힌 카드와 5가 적힌 카드를 뽑았을 경우 답은 1+3=4가 됩니다.
• 승현이가 처음에 3이 적힌 카드와 5가 적힌 카드를 뽑고, 다음에 1이 적힌 카드와 5가 적힌 카드를 뽑았을 경우 답은 3+1=4가 됩니다.

따라서 답은 4가 됩니다.

입력

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

출력

190