혼돈

도미노를 세워 놓고 쓰러뜨리는 놀이는 브라운 박사에게 너무 지루해졌다. 그래서 박사는 좀 더 수학적인 새 소일거리를 만들었다.

칠판에는 정수 $n$개가 적혀 있다. 박사는 다음 과정을 반복한다.

• 칠판에 적힌 세 수 $a$, $b$, $c$를 골라 지운다.
• 세 수 가운데 두 개를 골라 평균을 구한다. 합이 홀수면 내림한다. 이 값을 $d$라고 하자.
• 칠판에 $d$를 두 번 적는다.

칠판에 1, 2, 4가 적혀 있는 경우를 보자. 세 수를 모두 지운 뒤 박사는 1을 두 번(1과 2의 평균을 내림한 값), 2를 두 번(1과 4의 평균을 내림한 값), 3을 두 번(2와 4의 평균) 적을 수 있다. 칠판에 수가 두 개만 남으면 과정이 끝나고, 남은 두 수는 항상 같다.

마티는 박사를 지켜보면서 아무렇게나 고르는 것처럼 보인다고 생각했다. 박사는 그렇지 않다고 한다. 칠판에 남는 수가 최대가 되도록 골랐다는 것이다. 마티는 처음 적혀 있던 수를 기억해 두었다. 과정을 모두 끝냈을 때 칠판에 남는 두 수가 가질 수 있는 최댓값을 구하라.

첫째 줄에 칠판에 적힌 정수의 개수 $n$이 주어진다. ($3 \le n \le 10^5$)

둘째 줄에 칠판에 적힌 수 $a_i$가 $n$개 주어진다. ($1 \le a_i \le 10^9$)

박사가 과정을 모두 마친 뒤 칠판에 남는 두 수의 최댓값을 한 줄에 출력한다.