g4-08754. 科技节最大展号 · 林老师的题库

题目描述

学校科技节开幕，每个参展队都会领到一块数字牌，牌上写着一个非负整数（按通常写法，无前导零），第 $i$ 块牌上的数是 $a_{i}$ 。共有 $n$ 块数字牌。

闭幕式上，主持人要把这 $n$ 块牌子全部用上，排成一横排，从左到右连起来读成一个多位数。例如牌子为 $3$ 、 $31$ 、 $34$ 时，按 $34, 3, 31$ 的顺序排，读出 $34331$ ，这是能拼出的最大的数；而按 $3, 34, 31$ 排只能读出 $33431$ 。

请安排 $n$ 块牌子的顺序，使连起来读出的数最大，并输出这个数。

注意：若连接结果的最高位之前出现多余的 $0$ ，应当去掉这些前导零再输出；特别地，若所有牌子上都是 $0$ ，输出 $0$ 。

第一行一个整数 $n$ 。

第二行 $n$ 个非负整数 $a_{1}, a_{2}, \dots, a_{n}$ ，用空格分隔。

一行一个整数，表示能拼出的最大数（不含多余前导零）。

输入

4
32 357 3 0

输出

样例说明

直觉上 $32 > 3$ ，但把 $3$ 放在 $32$ 前面读出的数更大： $332 > 323$ 。最优排列是 $357, 3, 32, 0$ 。