/ 
Time Limit: 2 sec / Memory Limit: 256 MiB
配点 : 1000 点
問題文
シカのAtCoDeerくんは縦の長さが 1 の細長い長方形が N 個机に置いてあるのを見つけました。 机を二次元平面とみなすと、以下の図のように、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
部分点
- 1≦N≦400, 1≦l_i<r_i≦400 を満たすデータセットに正解した場合は、部分点として 300 点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
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 動かすのが最小です。
入力例 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
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