{"raw_statement":[{"iden":"problem statement","content":"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:\n![image](https://atcoder.jp/img/arc070/46b7dc61fc2016c9b45f10db46c6fce9.png)\nAtCoDeer 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."},{"iden":"constraints","content":"*   All input values are integers.\n*   $1≤N≤10^5$\n*   $1≤l_i<r_i≤10^9$"},{"iden":"partial score","content":"*   $300$ points will be awarded for passing the test set satisfying $1≤N≤400$ and $1≤l_i<r_i≤400$."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$l_1$ $r_1$\n$l_2$ $r_2$\n:\n$l_N$ $r_N$"},{"iden":"sample input 1","content":"3\n1 3\n5 7\n1 3"},{"iden":"sample output 1","content":"2\n\nThe second rectangle should be moved to the left by a distance of $2$."},{"iden":"sample input 2","content":"3\n2 5\n4 6\n1 4"},{"iden":"sample output 2","content":"0\n\nThe rectangles are already connected, and thus no move is needed."},{"iden":"sample input 3","content":"5\n999999999 1000000000\n1 2\n314 315\n500000 500001\n999999999 1000000000"},{"iden":"sample output 3","content":"1999999680"},{"iden":"sample input 4","content":"5\n123456 789012\n123 456\n12 345678901\n123456 789012\n1 23"},{"iden":"sample output 4","content":"246433"},{"iden":"sample input 5","content":"1\n1 400"},{"iden":"sample output 5","content":"0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}