A - Three Cards Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 枚のカードがあります。カードには 1 から N の番号がついています。

カード i には正整数 A_i が書かれています。

この中から 3 枚のカードを選び、好きな順で書かれている整数を連結し新しく整数を作ります。例えば、1,23,4 が書かれたカードを選んだとき、1234 や 4231 を作ることができます。

作ることのできる整数の最大値を求めてください。

制約

  • 3 \le N \le 2 \times 10^5
  • 1 \le A_i < 10^6
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

5
1 4 3 5 8

出力例 1

854

4,5,8 が書かれたカードを選んだ場合、458,485,548,584,845,854 を作ることができます。

855 以上の整数を作ることはできないので解は 854 です。

入力例 2

8
813 921 481 282 120 900 555 409

出力例 2

921900813

Score : 300 points

Problem Statement

There are N cards, numbered 1 to N.

Card i has a positive integer A_i written on it.

You can choose three of these cards and concatenate the integers written on them in any order you like to make a new integer. For example, if you choose cards with 1, 23, and 4 written on them, you can make integers such as 1234 and 4231.

Find the maximum integer you can make.

Constraints

  • 3 \le N \le 2 \times 10^5
  • 1 \le A_i < 10^6
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

5
1 4 3 5 8

Sample Output 1

854

If you choose cards with 4, 5, and 8 written on them, you can make 458, 485, 548, 584, 845, or 854.

You can make nothing greater than 854, so the answer is 854.

Sample Input 2

8
813 921 481 282 120 900 555 409

Sample Output 2

921900813