여기서 우리는 진수가 최종 보스를 공략할 수 있도록 도와주었고, 결국 진수는 최종 보스를 잡아내었다.

그러나 기쁨도 잠시, 던전 전체가 흔들리며 던전이 붕괴할 위험에 빠졌다. 엎친 데 덮친 격으로 하나뿐인 탈출구가 굳건히 닫혀 버렸다.

이는 최종 보스의 마지막 함정이었고, 아래와 같은 문제를 풀어야 탈출구를 열 열쇠를 구할 수 있었다.

• $1$ ~ $9$ 중 하나의 숫자가 적힌 카드 $c_1, c_2, ... , c_n$이 차례대로 주어진다.
• 카드가 주어질 때마다 그동안 받은 카드들의 왼쪽 또는 오른쪽에 놓아야 한다. 가장 처음 받은 카드는 중앙에 위치한다.
• 카드를 한 번 놓으면, 더 이상 그 카드에 손댈 수 없다.
• 최종적으로 놓인 카드들을 왼쪽에서 오른쪽으로 읽으면 $n$자리의 수가 하나 만들어진다.
• 이 수가 최종 보스가 미리 계산해 둔 수와 일치한다면 성공이다. 최종 보스는 항상 이 게임에서 만들 수 있는 가장 큰 수를 미리 계산해둔다.

진수는 모든 경우를 조사해 보려다 경우의 수가 $2^n$꼴임을 깨닫고, 우리에게 $c_1, c_2, ... , c_n$을 주며 도움을 요청하였다.

진수가 무사히 탈출할 수 있도록 게임에서 만들 수 있는 가장 큰 수를 어서 구해주도록 하자!

첫째 줄에 카드의 개수 $n$이 주어진다. $(1 ≤ n ≤ 200,000)$

둘째 줄에 $c_1, c_2, ... , c_n$이 공백으로 구분되어 주어진다. $(1 ≤ c_i ≤ 9)$