AT_arc147_c.[ARC147C] Min Diff Sum

有 $N$ 个人，编号为 $1,2,\ldots,N$，他们要被排列在数轴上。第 $i$ 个人的位置记为 $x_i$，其中 $x_i$ 必须是满足 $L_i \leq x_i \leq R_i$ 的整数。允许多个人站在同一个位置。

现在，将排列方式的不满度定义为：

$ \displaystyle\sum_{i=1}^{{N-1}\sum_{j=i+1}}{N}|x_j-x_i| $

请你求出所有可能的不满度中的最小值。

输入通过标准输入给出，格式如下：

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

请输出最小的不满度。

限制条件

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq L_i \leq R_i \leq 10^7 \ (1 \leq i \leq N)$
• 所有输入均为整数

样例解释 1

如果取 $x_1=3, x_2=4, x_3=5$，则不满度为 $4$。无法使不满度小于 $3$，所以输出 $4$。

由 ChatGPT 4.1 翻译