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도 회전시켰을 때 가장 큰 값을 갖게 되는 수를 출력한다.

제한

힌트