Largest Concatenated Integer

Given a list of non-negative integers, rearrange them such that they form the largest possible integer when concatenated together.

Note: The result may be very large, so you need to return a string instead of an integer.

For example, given the integers \( [3, 30, 34, 5, 9] \), the largest concatenated integer is 9534330.

The problem is essentially about ordering the numbers using a custom comparator. Consider two numbers \( x \) and \( y \). We define that \( x \) should come before \( y \) if the concatenation \( xy \) is greater than \( yx \), where \( xy \) denotes the string concatenation of \( x \) followed by \( y \). Use this logic to sort the list in descending order and then output the concatenated result.

If the resulting number has leading zeros, it should be reduced to a single zero (i.e. "0").

inputFormat

The first line of input contains an integer \( n \), 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.

1
5

5