21740번 - 도도의 수학놀이

길이가 N인 수열이 주어진다. 도도는 이 수열의 수를 이어붙여 180도 회전시켰을 때 가장 큰 수를 만들려고 한다. 각 숫자를 180도 회전시켰을 때 환원되는 숫자는 다음과 같다.

• $0$ -> $0$
• $1$ -> $1$
• $2$ -> $2$
• $5$ -> $5$
• $6$ -> $9$
• $8$ -> $8$
• $9$ -> $6$

숫자 $3$, $4$, $7$이 포함되어있는 수는 입력으로 주어지지 않는다. 모든 수를 이어붙인 수를 뒤집었을 때, 불필요한 $0$들은 제거된다. 단 한 번, 한 수를 두 번 사용할 수 있다.

이어붙인 수 중 180도 회전시켰을 때 가장 큰 값을 갖게 되는 수를 구하는 프로그램을 작성해보자.

첫째 줄에 정수 $N$ ($ 1 \leq N \leq 100\,000$)이 주어진다.

둘째 줄에는 길이가 $N$ 인 수열 $a$ ($ 1 \leq a_i \leq 1\,000\,000$)가 주어진다.

첫째 줄에 이어붙여 만든 수 중 180도 회전시켰을 때 가장 큰 값을 갖게 되는 수를 출력한다.