미니마 게임

앨리스와 밥은 최근에 아주 좋아하게 된 미니마 게임을 배웠습니다. 규칙은 다음과 같습니다.

탁자 위에 여러 장의 카드가 놓여 있고, 각 카드에는 양의 정수가 하나씩 적혀 있습니다. 두 사람은 번갈아 가며 차례를 진행하고, 앨리스가 먼저 시작합니다. 한 번의 차례에 플레이어는 탁자에서 카드를 원하는 만큼(한 장 이상) 가져갑니다. 이때 방금 가져간 카드들에 적힌 수 가운데 가장 작은 값만큼의 점수를 얻습니다. 탁자에서 마지막 카드가 사라지면 게임이 끝납니다.

두 플레이어 모두 자신의 총점에서 상대의 총점을 뺀 값을 최대로 만들고 싶어 합니다.

이 게임에는 최적 전략이 존재합니다. 주어진 카드들에 대해, 두 사람이 모두 최적으로 플레이했을 때의 결과를 구하세요.

첫째 줄에 카드의 개수를 나타내는 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다.

둘째 줄에는 카드에 적힌 $n$개의 양의 정수 $k_1, k_2, \dots, k_n$ ($1 \le k_i \le 10^9$)이 공백 하나로 구분되어 주어집니다.

두 사람이 모두 최적으로 플레이했을 때 앨리스가 밥을 앞서는 점수 차이를 정수 하나로 출력하세요. 만약 밥의 점수가 더 크다면 그 값은 음수가 됩니다.

예시에서 앨리스는 $3$이 적힌 카드 한 장을 가져가 $3$점을 얻습니다. 이어서 밥은 남은 두 장을 모두 가져가 $1$점(두 카드 중 더 작은 값)을 얻습니다. 게임이 $3$ 대 $1$로 끝나므로 앨리스가 $2$점 차이로 이깁니다.