题目描述

有 $N$ 个人，编号为 $1,2,\\ldots ,N$，他们要站在数轴上。我们用 $x_i$ 表示第 $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|$

求不满意度的最小可能值。

约束条件

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

输入

从标准输入读取输入数据，输入格式如下：

$N$

$L_1$ $R_1$

$L_2$ $R_2$

$\\vdots$

$L_N$ $R_N$

输出

输出答案。

示例输入1

3
1 3
2 4
5 6

示例输出1

4

如果我们令 $x_1=3,x_2=4,x_3=5$，那么不满意度为 $4$。我们无法使其小于或等于 $3$，因此答案是 $4$。

示例输入2

3
1 1
1 1
1 1

示例输出2

0

示例输入3

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

示例输出3

15