题目描述
有 N 个人,编号为 1,2,ldots,N,他们要站在数轴上。我们用 xi 表示第 i 个人所站的坐标。因此,xi 应该是一个整数,满足 LileqxileqRi。可以有多个人站在同一个坐标上。
我们定义不满意度如下公式:
displaystylesumi=1N−1sumj=i+1N∣xj−xi∣
求不满意度的最小可能值。
约束条件
- 2leqNleq3times105
- 1leqLileqRileq107,(1leqileqN)
- 输入中的所有值均为整数。
输入
从标准输入读取输入数据,输入格式如下:
N
L1 R1
L2 R2
vdots
LN RN
输出
输出答案。
示例输入1
示例输出1
如果我们令 x1=3,x2=4,x3=5,那么不满意度为 4。我们无法使其小于或等于 3,因此答案是 4。
示例输入2
示例输出2
示例输入3
示例输出3