세 번째로 작은 수

면접 대비

시간 제한1초메모리 제한128 MB

요약

서로 다른 자연수 n개가 주어질 때, 두 수를 순서 있게 이어 붙여 만들 수 있는 모든 수를 크기순으로 나열하고 세 번째로 작은 수를 출력한다.

난이도: 보통10점 중 6점
유형: 문자열, 정렬, 그리디, 완전 탐색
정답자: 아직 제출이 없습니다

문제

서로 다른 자연수 $n$ 개 $a_1, a_2, \dots, a_n$ 이 주어진다. 이 중에서 두 수를 순서 있게 골라(서로 다른 두 첨자 $i \ne j$ 를 정해 $a_i$ 를 앞, $a_j$ 를 뒤에 둔다) 이어 붙이면 새로운 수를 만들 수 있다.

예를 들어 $3$ 과 $4$ 를 이어 붙이면 $34$ 또는 $43$ 이 된다. 또한 $a_1 = 1$ , $a_4 = 11$ 을 이어 붙인 경우처럼, $a_i a_j$ 와 $a_j a_i$ 는 (붙이는 순서가 다르므로) 값이 같더라도 서로 다른 결과로 센다(둘 다 $111$ 이 되는 경우여도 마찬가지다).

이렇게 만들 수 있는 모든 수를 작은 것부터 크기 순으로 나열했을 때(같은 값이 여러 번 나오면 나온 횟수만큼 중복해서 센다) 세 번째로 작은 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 $n$ 이 주어진다 ( $3 \le n \le 108$ ). 다음 $n$ 개의 줄에 걸쳐 한 줄에 하나씩 $a_i$ 가 주어진다 ( $1 \le a_i \le 10000$ ). 주어지는 $n$ 개의 수는 모두 서로 다르다.

출력

세 번째로 작은 수를 한 줄에 출력한다.

예제2

예제 1
입력
```
3
2
7
5
```
예상 출력
```
52
```
예제 2
입력
```
4
17
888
1
71
```
예상 출력
```
171
```