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 20000)$. 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.