Problem:
 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≤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 1 3
1 3
5 7
1 3      Sample Output 1 2  The second rectangle should be moved to the left by a distance of 2 .       Sample Input 2 3
2 5
4 6
1 4      Sample Output 2 0  The rectangles are already connected, and thus no move is needed.       Sample Input 3 5
999999999 1000000000
1 2
314 315
500000 500001
999999999 1000000000      Sample Output 3 1999999680       Sample Input 4 5
123456 789012
123 456
12 345678901
123456 789012
1 23      Sample Output 4 246433       Sample Input 5 1
1 400      Sample Output 5 0

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from heapq import heappush, heappushpop

"""
・f(x) = （最上段の左端座標） -> 最小コスト
・g = newf とすると、g(x) = |x-l| + min_{x-w_{n-1}<=y<=x+w_n}f(y)
・常に [A0,B0] 上で定数、[A_i,A_{i-1}]で傾き-i、[B_{i-1},B_i]で傾きiの下に凸な折れ線
heapqで(A,B)の形で関数を持つ
・1段目の長方形で、A = [l], B = [l] からスタート（f(x) = |x - l|）
"""

N = int(readline())
m = map(int,read().split())
L,R = zip(*zip(m,m))

A = [-L[0]]; B = [L[0]]
addA = 0
addB = 0
min_f = 0
for n in range(1,N):
    p = R[n-1] - L[n-1]; q = R[n] - L[n]
    
    addA += (-q); addB += p
    a = -A[0] + addA
    b = B[0] + addB
    x = L[n]
    
    if x <= a:
        
        min_f += a - x
        heappush(A,-x + addA)
        y = -heappushpop(A,-x + addA) + addA
        heappush(B, y - addB)
    elif x >= b:
        
        min_f += x - b
        heappush(B, x - addB)
        y = heappushpop(B, x - addB) + addB
        heappush(A, -y + addA)
    else:
        
        heappush(A, -x + addA)
        heappush(B, x - addB)

print(min_f)

Solution (Python):
import sys
input = sys.stdin.readline
from heapq import heappop, heappush

"""
f(x) = （一番上の長方形の左端がxに来るときのコストの最小値） を関数ごと更新していきたい
更新後をg(x)とする
g(x) = |x-L| + min_{-width_1 \leq t\leq width_2} f(x+t), 前回の幅、今回の幅
常に、区間上で最小値を持ち傾きが1ずつ変わる凸な関数であることが維持される。（区間は1点かも）
傾きが変わる点の集合S_f = S_f_lower + S_f_upperを持っていく。
S_f_lower, S_upperは一斉に定数を足す：変化量のみ持つ
"""

N = int(input())
LR = [[int(x) for x in input().split()] for _ in range(N)]


L,R = LR[0]
S_lower = [-L]
S_upper = [L]
min_f = 0
add_lower = 0
add_upper = 0
prev_w = R - L

push_L = lambda x: heappush(S_lower, -x)
push_R = lambda x: heappush(S_upper, x)
pop_L = lambda: -heappop(S_lower)
pop_R = lambda: heappop(S_upper)

for L,R in LR[1:]:
    w = R - L
    
    add_lower -= w
    add_upper += prev_w
    
    
    x = pop_L() + add_lower
    y = pop_R() + add_upper
    a,b,c,d = sorted([x,y,L,L])
    push_L(a - add_lower)
    push_L(b - add_lower)
    push_R(c - add_upper)
    push_R(d - add_upper)
    min_f += c-b
    prev_w = w

print(min_f)

Solution (Python):
N = int(input())
P = [list(map(int, input().split())) for i in range(N)]
 
INF = 10**18
 
from heapq import heappush, heappop
 
l0, r0 = P[0]
 
L = [-l0+1]
R = [l0-1]
s = t = 0
 
res = 0
for i in range(N-1):
    l0, r0 = P[i]
    l1, r1 = P[i+1]
    s += (r1 - l1); t += (r0 - l0)
    if -s-L[0] <= l1-1 <= t+R[0]:
        heappush(L, -l1+1-s)
        heappush(R, l1-1-t)
    elif l1-1 < -s-L[0]:
        heappush(L, -l1+1-s)
        heappush(L, -l1+1-s)
        p = -heappop(L)-s
        heappush(R, p-t)
        res += (p - (l1-1))
    elif t+R[0] < l1-1:
        heappush(R, l1-1-t)
        heappush(R, l1-1-t)
        p = heappop(R) + t
        heappush(L, -p-s)
        res += (l1-1 - p)
print(res)

Solution (Python):

N = int(input())
P = [list(map(int, input().split())) for i in range(N)]

from heapq import heappush, heappop

l0, r0 = P[0]

L = [-l0+1]
R = [l0-1]
s = t = 0

res = 0
for i in range(N-1):
    l0, r0 = P[i]
    l1, r1 = P[i+1]
    s += (r1 - l1); t += (r0 - l0)
    if -s-L[0] <= l1-1 <= t+R[0]:
        heappush(L, -l1+1-s)
        heappush(R, l1-1-t)
    elif l1-1 < -s-L[0]:
        heappush(L, -l1+1-s)
        heappush(L, -l1+1-s)
        p = -heappop(L)-s
        heappush(R, p-t)
        res += (p - (l1-1))
    elif t+R[0] < l1-1:
        heappush(R, l1-1-t)
        heappush(R, l1-1-t)
        p = heappop(R) + t
        heappush(L, -p-s)
        res += ((l1-1) - p)
print(res)

Solution (Python):

N = int(input())
P = [list(map(int, input().split())) for i in range(N)]

INF = 10**18

from heapq import heappush, heappop

l0, r0 = P[0]

L = [-l0+1]
R = [l0-1]
s = t = 0

res = 0
for i in range(N-1):
    l0, r0 = P[i]
    l1, r1 = P[i+1]
    s += (r1 - l1); t += (r0 - l0)
    if -s-L[0] <= l1-1 <= t+R[0]:
        heappush(L, -l1+1-s)
        heappush(R, l1-1-t)
    elif l1-1 < -s-L[0]:
        heappush(L, -l1+1-s)
        heappush(L, -l1+1-s)
        p = -heappop(L)-s
        heappush(R, p-t)
        res += (p - (l1-1))
    elif t+R[0] < l1-1:
        heappush(R, l1-1-t)
        heappush(R, l1-1-t)
        p = heappop(R) + t
        heappush(L, -p-s)
        res += (l1-1 - p)
print(res)

Solution (Python):

N = int(input())
P = [list(map(int, input().split())) for i in range(N)]

INF = 10**18

from heapq import heappush, heappop

l0, r0 = P[0]

L = [-l0+1]
R = [l0-1]
s = t = 0

def debug(L, s, t, R):
    L0 = L[:]
    Q1 = []; Q2 = []
    while L0:
        Q1.append(-s-heappop(L0))
    R0 = R[:]
    while R0:
        Q2.append(t+heappop(R0))
    print("debug:", *Q1[::-1]+Q2)



res = 0
for i in range(N-1):
    l0, r0 = P[i]
    l1, r1 = P[i+1]
    
    s += (r1 - l1); t += (r0 - l0)
    if -s-L[0] <= l1-1 <= t+R[0]:
        
        heappush(L, -l1+1-s)
        heappush(R, l1-1-t)
        
    elif l1-1 < -s-L[0]:
        
        heappush(L, -l1+1-s)
        heappush(L, -l1+1-s)
        p = -heappop(L)-s
        
        heappush(R, p-t)
        
        
        res += (p - (l1-1))
    elif t+R[0] < l1-1:
        
        heappush(R, l1-1-t)
        heappush(R, l1-1-t)
        p = heappop(R) + t
        
        heappush(L, -p-s)
        
        res += (l1-1 - p)
    
    
print(res)