题目描述

有 $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$

输出格式

请输出最小的不满度。

样例 1

输入

3
1 3
2 4
5 6

输出

4

样例 2

输入

3
1 1
1 1
1 1

输出

0

样例 3

输入

6
1 5
2 4
1 1
4 4
3 6
3 3

输出

15

说明/提示

限制条件

• $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 翻译