题意

给你 $2 \times n$ 个整数 $a_i(0 \le a_i < m)$，你需要最小化将它们两两分组后每组之和对 $m$ 取模后的最大值。

$n \le 10^5,~m \le 10^9$

分析

看到让最大值最小化，我们先考虑二分最终的答案，每次检查是否存在一种方案使得配对后每对之和对 $m$ 取模后小于限制 $lim$。

考虑对于一个 $lim$，若存在合法方案，则将 $a_i$ 数组从小到大排序后一定有一种合法方案可以由下面的方法构造：

蓝色的边连接的两个点相加之和 $sum \in [0,~lim]$，绿色的边连接的两个点相加之和 $sum \in [M,~M+lim]$。该方案即为将序列从某一点断开为两个序列，左序列间全部使用蓝边进行匹配，右序列中全部使用绿边进行匹配。

考虑证明可以不存在蓝线与绿线相交的情况，假设存在四个位置 $i_1,~i_2,~i_3,~i_4$ 满足 $0 \le a[i_1]+a[i_3] \le lim,~m \le a[i_2]+a[i_4] \le m+lim$。

$a[i_2] \le a[i_3]$，所以 $0 \le a[i_1]+a[i_2] \le a[i_1]+a[i_3] \le lim$。
$a[i_3] \ge a[i_2]$，所以 $a[i_3]+a[i_4] \ge a[i_2]+a[i_4] \ge m$。而 $a[i_3] \le lim-a[i_1] \le lim,~a[i_4] \le m$，所以 $a[i_3]+a[i_4] \le m+lim$。

由于可以不存在蓝线与绿线相交的情况，所以我们可以将整个序列先分为左右两个序列，左序列内只连蓝线，右序列内只连绿线。

考虑证明同颜色线可以不相交，以左区间为例：假设存在四个位置 $i_1,~i_2,~i_3,~i_4$ 满足 $a[i_1]+a[i_3] \le lim,~a[i_2]+a[i_4] \le lim$。

所以在左右序列中不会出现有线相交的情况，即 $i$ 位置一定与 $len-i+1$ 位置匹配（$len$ 为序列长度）。

通过上面的证明我们可以确定该构造方案的合法性。

如果直接在二分答案中通过该方式判断限制是否合法，由于该方案中“将序列分为左右序列”操作需要再进行一次二分答案，所以总时间复杂度为 $O(nlgnlgm)$，可能可以通过本题（并没有试过）。

仔细分析发现先二分出答案再通过该构造方法判断合法性有较大的浪费，因为该构造方案不仅能够判断合法性，同时也可算出满足条件的最优答案。所以我们可以考虑直接通过二分找出最佳的断开左右序列的位置，计算该位置上的答案即可。

考虑找到一个尽量小的位置 $t$ 将原序列分为左右两个序列，同时满足两边序列都可以通过上述方法构造出方案，则该 $t$ 值对应的方案一定为最优方案。因为在左右序列均合法的前提下，$t$ 越小，左序列最大和与右序列最大和显然越小，即总答案一定越小。

二分出最小的符合条件的 $t$ 即可，时间复杂度 $O(nlgn)$。