分数: 600 点
问题陈述
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