NarrowRectangles

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$ ## 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$ ## Partial Score * $300$ points will be awarded for passing the test set satisfying $1≤N≤400$ and $1≤l_i<r_i≤400$. [samples]