Ghép Thành Số Lớn Nhất · canuc80k0334

Có $N$ tấm thẻ, mỗi thẻ ghi một số nguyên dương. Bạn phải xếp toàn bộ thẻ thành một hàng rồi đọc liền các biểu diễn thập phân từ trái sang phải, không chèn khoảng cách. Ví dụ, đặt thẻ $12$ trước thẻ $3$ tạo đoạn chữ số $123$ , còn đổi thứ tự tạo $312$ . Hãy tìm chuỗi chữ số biểu diễn số lớn nhất có thể thu được. Vì mọi $a_{i}$ dương, kết quả không có chữ số $0$ vô nghĩa ở đầu.

Input

Dòng đầu chứa số nguyên $N$ . Dòng thứ hai chứa $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ .

Output

In chuỗi chữ số lớn nhất tạo được sau khi dùng mỗi thẻ đúng một lần.

Constraints

$1 \leq N \leq 1 0^{4}$
$1 \leq a_{i} \leq 99$
Mỗi thẻ phải được dùng đúng một lần

Scoring

Subtask $1$ ( $50$ điểm): $N \leq 9$ .
Subtask $2$ ( $50$ điểm): Theo đầy đủ các giới hạn đã nêu.

Example

Test 1

Input

5
9 91 34 3 30

Output

99134330

Giải thích: So sánh từng cặp bằng hai cách ghép cho thứ tự $9, 91, 34, 3, 30$ . Ghép theo thứ tự đó tạo $99134330$ , lớn hơn mọi hoán vị khác.

Ý tưởng: Với hai chuỗi số x,y, phần trước và sau của chúng trong kết quả không đổi. Vì vậy chỉ cần so sánh xy với yx: cách ghép lớn hơn cho biết phần tử nào nên đứng trước.
Thuật toán: Đọc các số dưới dạng chuỗi. Sort bằng comparator x+y > y+x, sau đó nối các chuỗi theo thứ tự đã sort.
Chứng minh tính đúng đắn: Nếu hai phần tử kề x,y đang có yx>xy nhưng x đứng trước y, đổi chỗ chúng làm toàn bộ kết quả lớn hơn vì tiền tố và hậu tố giữ nguyên. Do đó một phương án tối ưu không thể có nghịch thế theo comparator. Thứ tự đã sort không có nghịch thế; từ bất kỳ hoán vị nào, đổi dần các cặp sai không làm giảm kết quả và dẫn đến một thứ tự sort. Vậy chuỗi thuật toán tạo ra là lớn nhất.
Độ phức tạp: O(N log N · L) thời gian, với L≤4 là độ dài hai chuỗi ghép khi so sánh; O(N) chuỗi bộ nhớ.