题目描述

AtCoDeer鹿在桌子上发现了$N$个矩形，每个矩形的高度为$1$。如果我们将桌子的表面视为二维平面，第$i$个矩形（$1≤i≤N$）覆盖了垂直范围\[i-1,i\]和水平范围\[l_i,r_i\]，如下图所示：

AtCoDeer将这些矩形水平移动，以实现所有矩形的连接。对于每个矩形，将其水平移动$x$的成本是$x$。找出实现连接的最小成本。可以证明，在问题的约束下，这个值总是一个整数。

约束条件

• 所有输入值都是整数。
• $1≤N≤10^5$
• $1≤l_i<r_i≤10^9$

输入

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

$N$ $l_1$ $r_1$ $l_2$ $r_2$ : $l_N$ $r_N$

输出

打印实现连接的最小成本。

示例输入 1

3
1 3
5 7
1 3

示例输出 1

2

第二个矩形应该向左移动$2$的距离。

示例输入 2

3
2 5
4 6
1 4

示例输出 2

0

这些矩形已经连接，因此不需要移动。

示例输入 3

5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000

示例输出 3

1999999680

示例输入 4

5
123456 789012
123 456
12 345678901
123456 789012
1 23

示例输出 4

246433

示例输入 5

1
1 400

示例输出 5

0