P6163 [Cnoi2020] Domain Limit

Cirno has $n$ integers, denoted as $a_1,a_2,a_3,...,a_n$. For each number $a_i$, there is a constraint pair $(l_i,r_i)$. Cirno wants to know: $$\min_{\forall t, a_t \in [l_t,r_t]}\big\{\sum_{i=1}^{n}\sum_{j=1}^{n}\left| a_i - a_j \right|\big\}$$

The first line contains an integer $n$. The next $n$ lines each contain a constraint pair $(l_i,r_i)$.

One line containing an integer, which is the answer.

### Sample 1 Explanation When $(a_1,a_2,a_3)=(2,3,3)$, the answer reaches its minimum. ### Constraints and Notes **"This problem uses bundled testdata."** - Subtask 1 ( $20\%$ ): $n \le 10$, and $r_i - l_i \le 5$. - Subtask 2 ( $20\%$ ): $n \le 20$. - Subtask 3 ( $20\%$ ): $n \le 10^3$. - Subtask 4 ( $40\%$ ): $n \le 10^5$. For $100\%$ of the testdata: $n \in (0,10^5]$, $0 \le l_i \le r_i \le 10^9$, and the answer is within $[0,4 \times 10^{18}]$. Translated by ChatGPT 5