Largest Concatenated Integer

Given a list of non-negative integers, your task is to arrange them so that they form the largest possible concatenated number. For example, given the numbers [50, 2, 1], the largest concatenation is "5021".

The trick is to recognize that simple numerical sorting does not work. Instead, you must sort the numbers based on the order in which they produce the maximum combined result. Formally, for any two numbers \(a\) and \(b\), you should compare the two strings \(a\,b\) and \(b\,a\) (concatenation of the two numbers in different orders) and decide their order based on which is larger in lexicographical order.

Note: The result should not have extra leading zeroes. In cases where all numbers are zero, the output should be "0".

inputFormat

The first line contains a single integer \(n\) which represents the number of integers. The second line contains \(n\) space-separated non-negative integers.

outputFormat

Output a single line containing the largest concatenated integer as a string.

3
50 2 1

5021