/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。A の異なる 2 要素を選び、それらを文字列として結合して得られる N(N-1) 個（重複を含む）の整数の中央値、すなわち N(N-1)/2 番目に小さい値を求めてください。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^8
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
3 1 23 45
出力例 1
231
A=(1, 23, 45) の異なる 2 要素を選び、それらを文字列として結合して得られる整数は、 (123, 145, 231, 451, 2345, 4523) の 6 個です。3 番目に小さい 231 を出力します。
入力例 2
3 2 2 4
出力例 2
24
A=(2, 2, 4) の異なる 2 要素を選び、それらを文字列として結合して得られる整数は、 (22, 22, 24, 24, 42, 42) の 6 個です。3 番目に小さい 24 を出力します。
入力例 3
2 100000000 100000000
出力例 3
100000000100000000
答えは 32-bit 整数に収まらないことがあることに注意してください。
Problem Statement
You are given a length-N sequence of positive integers A=(A_1,A_2,\dots,A_N). Among the N(N-1) integers (including duplicates) obtained by choosing two distinct elements from A and concatenating them as strings, find the median, or the \left( N(N-1)/2 \right)-th smallest value.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^8
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
3 1 23 45
Sample Output 1
231
By choosing two distinct elements from A=(1, 23, 45) and concatenating them as strings, six integers can be obtained: (123, 145, 231, 451, 2345, 4523). Print the 3-rd smallest integer 231.
Sample Input 2
3 2 2 4
Sample Output 2
24
By choosing two distinct elements from A=(2, 2, 4) and concatenating them as strings, six integers can be obtained: (22, 22, 24, 24, 42, 42). Print the 3-rd smallest integer 24.
Sample Input 3
2 100000000 100000000
Sample Output 3
100000000100000000
Note that the answer may not fit into a 32-bit integer type.