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≤i≤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≤N≤10^5
 - 1≤l_i<r_i≤10^9

-----Partial Score-----
 - 300 points will be awarded for passing the test set satisfying 1≤N≤400 and 1≤l_i<r_i≤400.

-----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.

-----Sample Input-----
3
1 3
5 7
1 3

-----Sample Output-----
2

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

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\ninput = sys.stdin.readline\nfrom heapq import heappop, heappush\n\n"""\nf(x) = （一番上の長方形の左端がxに来るときのコストの最小値） を関数ごと更新していきたい\n更新後をg(x)とする\ng(x) = |x-L| + min_{-width_1 \\leq t\\leq width_2} f(x+t), 前回の幅、今回の幅\n常に、区間上で最小値を持ち傾きが1ずつ変わる凸な関数であることが維持される。（区間は1点かも）\n傾きが変わる点の集合S_f = S_f_lower + S_f_upperを持っていく。\nS_f_lower, S_upperは一斉に定数を足す：変化量のみ持つ\n"""\n\nN = int(input())\nLR = [[int(x) for x in input().split()] for _ in range(N)]\n\n# initialize\nL,R = LR[0]\nS_lower = [-L]\nS_upper = [L]\nmin_f = 0\nadd_lower = 0\nadd_upper = 0\nprev_w = R - L\n\npush_L = lambda x: heappush(S_lower, -x)\npush_R = lambda x: heappush(S_upper, x)\npop_L = lambda: -heappop(S_lower)\npop_R = lambda: heappop(S_upper)\n\nfor L,R in LR[1:]:\n    w = R - L\n    # 平行移動とのminをとるステップ\n    add_lower -= w\n    add_upper += prev_w\n    # abs(x-L) を加えるステップ\n    # abs は瞬間に2傾きが変わるので\n    x = pop_L() + add_lower\n    y = pop_R() + add_upper\n    a,b,c,d = sorted([x,y,L,L])\n    push_L(a - add_lower)\n    push_L(b - add_lower)\n    push_R(c - add_upper)\n    push_R(d - add_upper)\n    min_f += c-b\n    prev_w = w\n\nprint(min_f)\n\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13323