Score : $1000$ points

Problem Statement

AtCoDeer the deer found $N$ rectangle lying on the table, each with height $1$. If we consider the surface of the desk as a two-dimensional plane, the $i$-th rectangle $i(1 \leq i \leq N)$ covers the vertical range of $[i-1,i]$ and the horizontal range of $[l_i,r_i]$, as shown in the following figure:

AtCoDeer will move these rectangles horizontally so that all the rectangles are connected. For each rectangle, the cost to move it horizontally by a distance of $x$, is $x$. Find the minimum cost to achieve connectivity. It can be proved that this value is always an integer under the constraints of the problem.

Constraints

• All input values are integers.
• $1 \leq N \leq 10^5$
• $1 \leq l_i

Partial Score

• $300$ points will be awarded for passing the test set satisfying $1 \leq N \leq 400$ and $1 \leq l_i.

Input

The input is given from Standard Input in the following format:

$N$

$l_1$ $r_1$

$l_2$ $r_2$

:

$l_N$ $r_N$

Output

Print the minimum cost to achieve connectivity.

3
1 3
5 7
1 3

2

The second rectangle should be moved to the left by a distance of $2$.

3
2 5
4 6
1 4

0

The rectangles are already connected, and thus no move is needed.

5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000

1999999680

5
123456 789012
123 456
12 345678901
123456 789012
1 23

246433

1
1 400

0