Largest Number Concatenation

You are given a list of non-negative integers. Your task is to arrange them such that they form the largest possible number when concatenated together. For example, given the list [54, 546, 548], the largest concatenation is 54854654. If the resulting number has leading zeros, output just "0" instead. This problem tests your ability to manipulate strings and custom sort orders using greedy algorithms.

Note: When comparing two numbers (as strings) a and b, compare the concatenated results a+b and b+a. The order which produces a larger combined number should come first in the sorted order. Formally, for two strings a and b, if \(a+b < b+a\), then b should precede a.

inputFormat

The first line of input contains an integer n which represents the number of non-negative integers. If n > 0, the second line contains n space-separated non-negative integers. If n = 0, the second line is omitted.

outputFormat

Output a single line containing the largest number that can be formed by concatenating the given integers. The answer should be output as a string.

1
9

9