Micro and Permutation

3.4

21 votes
Easy
Problem

Micro has just learned about permutations. So he went to Ravi's room to boast about it. But Ravi is very smart, he instead gave him a problem to solve. He gave him an array A of integers of size N. Now Micro has to find a permutation of the numbers such that the number formed by concatenating the numbers of array from left to right is maximized ( see sample explanation for more clarity).

Input:
First line consists of N the size of array. Second line consists of N space separated denoting the array.

Output:
Print the maximum number that is formed by concatenating the numbers of array. (See sample output).

Constraints:
1 ≤ N ≤ 10^5
1 ≤ A[i] ≤ 10^9

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

There are six permutations possible:
4, 32, 9. Number formed = 4329
4, 9, 32. Number formed = 4932
9, 4, 32. Number formed = 9432
9, 32, 4. Number formed = 9324
32, 9, 4. Number formed = 3294
32, 4, 9. Number formed = 3249
Clearly the maximum number is 9432

Editor Image

?