A. 商店送货II

传统题

1000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_{1}$ ∼ $A_{N}$ 。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。为了提高效率，降低成本，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

第一行输入整数 $N$

第二行 $N$ 个整数 $A_{1}$ ∼ $A_{N}$

输出货仓建立的最佳位置（如果有多个点，输出最小 $A_{i}$ 值所在的位置；如果 $A_{i}$ 值相同，输出靠前的 $A_{i}$ 值所在位置）

4
6 2 9 1

$1\leqslant N \leqslant 10^{5},0\leqslant A_{i}\leqslant 4\times 10^{4}$

《算法竞赛进阶指南》