한 대회에 \(N\)명의 선수가 참가한다. 각 선수에게는 실력을 나타내는 점수가 하나씩 주어진다.

대회 운영진은 모든 선수를 두 팀으로 나누려고 한다. 모든 선수는 정확히 한 팀에 속해야 하며, 두 팀의 인원수 차이는 1 이하여야 한다.

두 팀의 실력 점수 합 차이가 최소가 되도록 선수들을 나누었을 때, 두 팀의 실력 점수 합을 구하는 프로그램을 작성하시오.

\(N\)이 홀수라면 한 팀에는 \(\lfloor N/2 \rfloor\)명, 다른 팀에는 \(\lceil N/2 \rceil\)명이 속한다. \(N=1\)이면 한 팀이 비어 있을 수 있다.

입력

첫째 줄에 선수의 수 \(N\)이 주어진다.

다음 \(N\)개의 줄에 선수들의 실력 점수 \(S_i\)가 한 줄에 하나씩 주어진다.

출력

두 팀의 실력 점수 합을 작은 값부터 공백으로 구분하여 출력한다.

제한 사항

• \(1 \le N \le 100\)
• \(1 \le S_i \le 450\)

예제 입력 1

4
30
40
50
60

예제 출력 1

90 90

예제 설명 1

점수가 30, 60인 선수를 한 팀으로, 점수가 40, 50인 선수를 다른 팀으로 나누면 두 팀의 인원수는 각각 2명이고 점수 합은 모두 90이다.

예제 입력 2

3
1
2
100

예제 출력 2

3 100