Canadian Computing Competition: 2005 Stage 2, Day 2, Problem 2

You are to find the length of the shortest path from the top to the bottom of a grid covering specified points along the way.

More precisely, you are given an ~n~ by ~n~ grid, rows ~1 \dots n~ and columns ~1 \dots n~ ~(1 \le n \le 20\,000)~. On each row ~i~, two points ~L(i)~ and ~R(i)~ are given where ~1 \le L(i) \le R(i) \le n~. You are to find the shortest distance from position ~(1, 1)~, to ~(n, n)~ that visits all of the given segments in order. In particular, for each row ~i~, all the points

$$\displaystyle (i, L(i)), (i, L(i)+1), \dots, (i, R(i)-1), (i, R(i))$$

must be visited. Notice that one step is taken when dropping down between consecutive rows. Note that you can only move left, right and down (you cannot move up a level). On finishing the segment on row ~n~, you are to go to position ~(n,n)~, if not already there. The total distance covered is then reported.

Input Specification

The first line of input consists of an integer ~n~, the number of rows/columns on the grid. On each of the next ~n~ lines, there are two integers ~L(i)~ followed by ~R(i)~ (where ~1 \le L(i) \le R(i) \le n~).

Output Specification

The output is one integer, which is the length of the (shortest) path from ~(1, 1)~ to ~(n, n)~ which covers all intervals ~L(i), R(i)~.

Sample Input

6
2 6
3 4
1 3
1 2
3 6
4 5

Sample Output

24

Explanation for Sample Output

Below is a pictorial representation of the input.

1       2       3       4       5       6
.       _________________________________
                ________
_________________
_________
                _________________________
                        _________       .

Notice that on the first row, we must traverse ~5~ units to the right and then drop down one level.

On the second row, we must traverse ~3~ units to the left and drop down one level.

On the third row, we must traverse ~2~ units to the left and drop down one level.

On the fourth row, we move ~1~ unit to the right and then drop down one level.

On the fifth row, we move ~4~ units to the right and drop down one level.

On the sixth (and final) row, we move ~2~ units left, then ~2~ units right.

In total, we have moved ~6+4+3+2+5+4 = 24~ units.