P14739 [ICPC 2021 Seoul R] John' s Gift

每天早晨，店主 John 会收到 $n$ 件价值各不相同的商品，以及 $n$ 张价格互不相同的价签。John 希望尽可能多地售出商品，因此他会在商品和价签之间建立一个配对，以最小化配对中两者差值的最大值（简称为 max-difference），且不同的商品必须与不同的价签配对。例如，若 John 有两件价值分别为 $10$ 和 $30$ 的商品，以及两张价格分别为 $10$ 和 $20$ 的价签，那么通过配对 $(10, 10)$ 和 $(30, 20)$，可以将 max-difference 最小化为 $10$。这个最小的 max-difference 被称为 **匹配得分**。 今天，John 的朋友 Jane 要举办生日派对，John 决定从他的商品中挑选一件作为生日礼物。在选择商品时，他不希望损失太多利润，因此希望选择一件商品，使得将其移除后，剩下的 $n-1$ 件商品与原有的 $n$ 张价签之间能够获得最小的匹配得分。顺便一提，在匹配 $n-1$ 件商品时，John 会留下一张价签不参与配对，以形成合理的匹配。 例如，John 有两件商品 $G_1$ 和 $G_2$，其价值分别为 $10$ 和 $30$，以及两张价签，价格分别为 $10$ 和 $20$。如果他选择 $G_1$ 作为礼物，那么 $G_2$ 可能的定价是 $10$ 或 $20$。当 $G_2$ 定价为 $20$ 时，匹配得分为 $10$。另一方面，如果他选择 $G_2$ 作为礼物，那么当 $G_1$ 定价为 $10$ 时，匹配得分为 $0$。因此，为了获得最小的匹配得分，John 会选择 $G_2$ 作为礼物。换句话说，在 $n$ 件商品中，John 可以选择任意一件作为礼物，这将定义出剩下的 $n-1$ 件商品与 $n$ 张价签之间的一个新的匹配得分。在 $n$ 种可能的礼物选择中，John 希望找到一件商品，其移除后能产生最小的匹配得分。 给定 $n$ 件商品的价值和 $n$ 张价签的价格，编写一个程序，输出 John 为了使得剩下的 $n-1$ 件商品与 $n$ 张价签之间的匹配得分最小，所应挑选的礼物的价值。如果存在两个或更多候选商品，则输出候选商品中价值最小的那个。

你的程序需要从标准输入读取数据。输入的第一行包含一个整数 $n$ ($2 \le n \le 10^6$)，其中 $n$ 表示商品和价签的数量。第二行包含 $n$ 个互不相同正整数，表示 $n$ 件商品的价值。第三行包含 $n$ 个互不相同的正整数，表示 $n$ 张价签的价格。商品价值和价签价格均不超过 $10^9$。

你的程序需要向标准输出写入结果。输出恰好一行。该行应包含 John 为 Jane 的生日礼物所挑选的商品的价值，该商品的移除将使得剩下的 $n-1$ 件商品获得最小的匹配得分。如果有多个候选商品，则输出候选商品中价值最小的那个。

翻译由 DeepSeek V3 完成