← 返回题目列表

AtCoder · past20_m

M. 连接的中值

中文机器翻译题面 查看原题

问题陈述

给你一个长度-N 正整数序列 A=(A_1,A_2,\dots,A_N)。其中 N(N-1) 通过选择两个不同元素获得的整数(包括重复项) A 并将它们连接为字符串,找到中位数,或者 \left( N(N-1)/2 \right)- 第一个最小值。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^8
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

打印答案。


示例输入 1

3
1 23 45

示例输出 1

231

通过选择两个不同的元素 A=(1, 23, 45) 并将它们连接成字符串,可以得到六个整数: (123, 145, 231, 451, 2345, 4523)。打印 3-rd 最小整数 231.


示例输入 2

3
2 2 4

示例输出 2

24

通过选择两个不同的元素 A=(2, 2, 4) 并将它们连接成字符串,可以得到六个整数: (22, 22, 24, 24, 42, 42)。打印 3-rd 最小整数 24.


示例输入 3

2
100000000 100000000

示例输出 3

100000000100000000

请注意,答案可能不适合 32 位整数类型。