도도의 수학놀이

시간 제한2초메모리 제한1024 MB

요약

0,1,2,5,6,8,9로만 이루어진 수열을 모두 이어붙이되 한 수를 두 번 쓸 수 있을 때, 이어붙인 수를 180도 회전하고 앞의 0을 지운 값이 최대가 되도록 만든다.

문제

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

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

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

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

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

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