Largest Concatenated Number

You are given n non-negative integers. Your task is to arrange them in such a manner that they form the largest possible number when concatenated together.

More formally, let \(S = [a_1, a_2, \ldots, a_n]\) be the sequence of integers. You need to reorder \(S\) so that the concatenated number \(a_{i_1}a_{i_2}\ldots a_{i_n}\) is maximized. Note that if the numbers form a result with extra leading zeros, you should output a single 0.

Example:

• For input 3 30 34 5 9, the largest number is 9534330.

The solution may involve a custom comparator that compares two numbers based on the concatenation order. For two numbers \(x\) and \(y\), consider the two possible orders \(xy\) and \(yx\) (where the numbers are converted to strings). The order which results in a higher value should come first in the final output.

In mathematical terms, for two string representations \(x\) and \(y\), if \(x+y > y+x\) (in lexicographical order), then \(x\) should appear before \(y\) in the sorted sequence.

inputFormat

The first line of input contains an integer \(n\) representing the number of integers.

The second line contains \(n\) space-separated non-negative integers.

Example:

5
1 2 3 4 5

outputFormat

Output a single line containing the largest number that can be formed by concatenating the given integers.

If the concatenated result begins with zero, output just 0.

## sample

5
1 2 3 4 5

54321