시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 1024 MB 563 64 41 17.083%

문제

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

예제 입력 1

4
1 6 8 9

예제 출력 1

19866