Background

An elevator is a space that gives people plenty of time to think.

Problem Description

Given two arrays $a, b$ of length $n$. We say a sequence $p$ is valid. Let the length of $p$ be $m$. The sequence $p$ is valid if and only if:

• $p_1 = 1$.
• For all $1 \le i < m$, we have $|p_i - p_{i+1}| = 1$.
• For all $1 \le k \le n$, there exists an ordered pair $(i, j)$ such that $1 \le i < j \le m$, $p_i = a_k$, and $p_j = b_k$.

You need to output, among all valid sequences $p$, the minimum possible length of $p$.

Input Format

The first line contains an integer $n$.

The next $n$ lines each contain two integers $a_i, b_i$.

Output Format

Output one integer, the minimum length of $p$ among all valid sequences $p$.

2
3 2
2 5

7

4
4 7
10 8
9 11
4 2

18

Hint

[Sample Explanation #1]

The minimum length of $p$ is $7$. One such sequence $p$ is $\{1,2,3,2,3,4,5\}$.

[Constraints]

For all testdata, $1 \le n \le 5\times10^5$, $1 \le a_i, b_i \le 10^9$, and it is guaranteed that $a_i \neq b_i$.

This problem uses bundled testdata.

Translated by ChatGPT 5