Description

On an $n \times n$ grid, there is a line segment in each row. In row $i$, the segment’s left endpoint is $(i, L_i)$ and its right endpoint is $(i, R_i)$.

You start from $(1, 1)$, must traverse all the segments along the way, and finally reach $(n, n)$, with the total distance traveled as short as possible.

More specifically, at any time you may only move one step down (row index increases by $1$), one step left (column index decreases by $1$), or one step right (column index increases by $1$). Since you cannot move up, when moving down from any row to the next, you must ensure you have already completely traversed the segment in the current row.

Input Format

The first line contains an integer $n$.

Each of the next $n$ lines contains two integers. In the $i$-th of these lines (the overall $(i+1)$-th line), the integers denote $L_i$ and $R_i$.

Output Format

Output a single integer: the length of the shortest route.

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

24

Hint

One chosen route is:

 (1, 1) (1, 6)
 (2, 6) (2, 3)
 (3, 3) (3, 1)
 (4, 1) (4, 2)
 (5, 2) (5, 6)
 (6, 6) (6, 4) (6, 6)

It is not hard to compute that the total length is $24$.

Constraints: For $100\%$ of the testdata, $1 \le n \le 2 \times 10^4$, $1 \le L_i \le R_i \le n$.

Translated by ChatGPT 5