P9579 "Cfz Round 1" Elevator

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

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

The first line contains an integer $n$. The next $n$ lines each contain two integers $a_i, b_i$.

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

#### [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.** |Subtask ID|Points|$n \le$|Special Property| |:---:|:---:|:---:|:---:| |$1$|$9$|$1$|None| |$2$|$9$|$5\times10^5$|Guaranteed $a_i < b_i$| |$3$|$21$|$5\times10^5$|$a_i, b_i$ are generated uniformly at random in $[1,10^9]$| |$4$|$27$|$2000$|None| |$5$|$34$|$5\times10^5$|None| Translated by ChatGPT 5