Make the Largest Number

Interview

Time limit2sMemory limit512 MB

Summary

Given up to 1000 non-negative integers, order the pieces so their concatenation is the largest possible number, and print it without leading zeros.

Level: Medium4 of 10
Topics: Greedy, Sorting, String
Solved: No attempts yet

Problem

You are given a list of N non-negative integers. Write a program that finds the largest number that can be formed by arranging the numbers in the list.

Input

The first line gives the number of integers N (1 ≤ N ≤ 1,000). The second line gives the numbers in the list. The numbers are separated by spaces and are non-negative integers less than or equal to 1,000,000,000. Every number except 0 does not start with 0, and if 0 appears, it appears as a single 0.

Output

Print the largest number that can be formed by arranging the numbers in the list. The number must not start with 0, and if the answer is 0, you must print a single 0.

Examples2

Example 1
Input
```
5
3 30 34 5 9
```
Expected output
```
9534330
```
Example 2
Input
```
5
0 0 0 0 1
```
Expected output
```
10000
```