Largest Number Formation

Given a list of non-negative integers, arrange them such that the number formed is the largest possible. In other words, for an array \(A = [a_1, a_2, \dots, a_n]\), you need to reorder the elements so that when concatenated, they form the maximum possible numerical value.

The key idea is to compare two numbers \(a\) and \(b\) by checking which of the two concatenated strings \(a\parallel b\) and \(b\parallel a\) forms a larger number. For example, given the array [3, 30, 34, 5, 9], the largest number possible is 9534330.

Note: If the result begins with '0', it means all the numbers are zeros and you should output "0".

inputFormat

The input is provided via standard input (stdin). The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)) representing the number of integers. The second line contains \(n\) non-negative integers separated by spaces.

outputFormat

The output is a single line string representing the largest number that can be formed by concatenating the given integers.

5
3 30 34 5 9

9534330