upper_bound 时找的应该是 $\dfrac{sum_t}{2}$ 而不是 $\dfrac{n}{2}$。

注意最后 check 时距离和最大值可达 $5\times10^{19}$，注意开 unsigned long long。