Largest Number Concatenation

Given a list of non-negative integers, arrange them such that they form the largest possible number when concatenated. In other words, you need to reorder the numbers to maximize the concatenated string result. For example, given the list [10, 2], the largest number is 210.

To solve this problem, you should compare two numbers by checking which concatenation — the first number followed by the second or vice versa — yields a larger string in lexicographical order. The final output should not contain any unnecessary leading zeros; if all the numbers are zero, output just 0.

Note: When a formula is needed, express it in LaTeX format. For instance, when comparing two strings a and b, we choose a before b if (a+b \gt b+a).

inputFormat

The first line of the input contains a single integer (n) (the number of elements). The second line contains (n) non-negative integers separated by spaces.

outputFormat

Output a single string representing the largest possible number obtained by concatenating the given integers.## sample

1
9

9