Largest Number Concatenation

Given \(n\) positive integers \(a_1, a_2, \ldots, a_n\), arrange them in such an order that after concatenation, the resulting number is as large as possible. Formally, determine a permutation \((i_1, i_2, \ldots, i_n)\) such that the number \[ \text{result} = a_{i_1}a_{i_2}\ldots a_{i_n} \] is maximized.

inputFormat

The input consists of two lines:

• The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the number of integers.
• The second line contains \(n\) space-separated positive integers \(a_i\) (\(1 \le a_i \le 10^9\)).

outputFormat

Output the largest number that can be formed by concatenating the given integers.

sample

3
10 2 9

9210