output_description: Print the minimum cost to achieve connectivity.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N
      l_1 r_1
      l_2 r_2
      :
      l_N r_N
attempt: 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)]
  
  # initialize
  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
      # 平行移動とのminをとるステップ
      add_lower -= w
      add_upper += prev_w
      # abs(x-L) を加えるステップ
      # abs は瞬間に2傾きが変わるので
      x = pop_L() + add_lower
      y = pop_R() + add_upper
      x, y, z, w = sorted([x, y, L, L])
      push_L(x - add_lower)
      push_L(y - add_lower)
      push_R(z - add_upper)
      push_R(w - add_upper)
      min_f += z - y
  
  print(min_f)
  
problem_description: 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:
  
  ![](https://atcoder.jp/img/arc070/46b7dc61fc2016c9b45f10db46c6fce9.png)
  
  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.
samples: [{"input": "3\n    1 3\n    5 7\n    1 3", "output": "2\n    \n\nThe second rectangle should be moved to the left by a distance of 2.\n\n* * *"}, {"input": "3\n    2 5\n    4 6\n    1 4", "output": "0\n    \n\nThe rectangles are already connected, and thus no move is needed.\n\n* * *"}, {"input": "5\n    999999999 1000000000\n    1 2\n    314 315\n    500000 500001\n    999999999 1000000000", "output": "1999999680\n    \n\n* * *"}, {"input": "5\n    123456 789012\n    123 456\n    12 345678901\n    123456 789012\n    1 23", "output": "246433\n    \n\n* * *"}, {"input": "1\n    1 400", "output": "0"}]