CF1817E Half-sum

You're given a multiset of non-negative integers $ \{a_1, a_2, \dots, a_n\} $ . In one step you take two elements $ x $ and $ y $ of the multiset, remove them and insert their mean value $ \frac{x + y}{2} $ back into the multiset. You repeat the step described above until you are left with only two numbers $ A $ and $ B $ . What is the maximum possible value of their absolute difference $ |A-B| $ ? Since the answer is not an integer number, output it modulo $ 10^9+7 $ .

N/A

N/A

In the first case, you can't do any operations, so the answer is $ |7-3|=4 $ . In the second case, one of the optimal sequence of operations: 1. Substitute $ 1 $ and $ 2 $ with $ 1.5 $ ; 2. Substitute $ 10 $ and $ 11 $ with $ 10.5 $ ; 3. The difference between $ 1.5 $ and $ 10.5 $ is $ 9 $ . In the third case, the exact answer is $ \frac{3}{2} $ , and $ 500\,000\,005 \cdot 2 \equiv 3 \pmod{10^9+7} $ .