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...n and columns 1...n (1 ≤ n ≤ 20000). On each row i, two points L(i) and R(i) are given where 1 ≤ L(i) ≤ R(i) ≤ 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 (i,L(i));(i,L(i)+1),(i,L(i)+2),...,(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 Input file contains maximum 10 sets of inputs. The description of each set is given below: The first line of each set 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 ≤ L(i) ≤ R(i) ≤ n). Input is terminated by a set whose value of n is zero. This input should not be processed. Output For each set of input 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). Explanation of Sample Input/Output Below is a pictoral representation of the input. 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.
2/2 Sample Input 6 26 34 13 12 36 45 0 Sample Output 24