Problem Description

拼数

题目背景

NOIP1998 提高组 第二题

题目描述

设有 $n$ 个正整数 $a_1 \dots a_n$，请将它们连接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数 $n$。

第二行有 $n$ 个整数，表示给出的 $n$ 个整数 $a_i$。

输出格式

一个正整数，表示最大的整数。

样例

样例 1

输入

3
13 312 343

输出

34331213

样例 2

输入

4
7 13 4 246

输出

7424613

提示

样例 1 说明

三个数字接成 $34331213$ 时最大：先接 $343$，再接 $312$，最后接 $13$。

样例 2 说明

最大接法是 $7 \to 4 \to 246 \to 13$，得到 $7424613$。

关键提示

不要按数字大小排序，而要按"拼接后更大"来排序：若 $x + y > y + x$（按字符串拼接比较），则 $x$ 应排在 $y$ 前面。这个比较满足传递性，可以直接作为排序关键字。

数据规模与约定

对于全部的测试点，保证 $1 \le n \le 20$，$1 \le a_i \le 10^9$。