{"problem":{"name":"「Cfz Round 1」Elevator","description":{"content":"给定两个长度为 $n$ 的数组 $a,b$。我们称序列 $p$ 是满足条件的，设 $p$ 的长度为 $m$，当且仅当： - $p_1=1$；   - 对于所有的 $1\\le i<m$，都有 $|p_i-p_{i+1}|=1$；   - 对于所有的 $1\\le k\\le n$，都存在一个有序数对 $(i,j)$，满足 $1 \\le i < j \\le m$ 且 $p_i=a_k$，$p_j=b_k","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9579"},"statements":[{"statement_type":"Markdown","content":"给定两个长度为 $n$ 的数组 $a,b$。我们称序列 $p$ 是满足条件的，设 $p$ 的长度为 $m$，当且仅当：\n\n- $p_1=1$；  \n- 对于所有的 $1\\le i<m$，都有 $|p_i-p_{i+1}|=1$；  \n- 对于所有的 $1\\le k\\le n$，都存在一个有序数对 $(i,j)$，满足 $1 \\le i < j \\le m$ 且 $p_i=a_k$，$p_j=b_k$。\n\n你需要输出所有满足条件的序列 $p$ 中，$p$ 的长度的最小值。\n\n## Input\n\n第一行一个整数 $n$。\n\n接下来 $n$ 行，第 $i$ 行两个整数 $a_i,b_i$。\n\n## Output\n\n一个整数，表示所有满足条件的序列 $p$ 中，$p$ 的长度的最小值。\n\n[samples]\n\n## Background\n\n电梯是一个可以让人充分思考的空间。\n\n## Note\n\n#### 【样例解释 #1】\n\n序列 $p$ 的长度的最小值为 $7$，此时的序列 $p$ 为 $\\{1,2,3,2,3,4,5\\}$。\n\n#### 【数据范围】\n\n对于所有数据，$1 \\le n \\le 5\\times10^5$，$1 \\le a_i,b_i \\le 10^9$，保证 $a_i \\neq b_i$。\n\n**本题采用捆绑测试。**\n\n|子任务编号|分值|$n \\le$|特殊性质|\n|:---:|:---:|:---:|:---:|\n|$1$|$9$|$1$|无|\n|$2$|$9$|$5\\times10^5$|保证 $a_i < b_i$|\n|$3$|$21$|$5\\times10^5$| $a_i,b_i$ 在 $[1,10^9]$ 内随机生成|\n|$4$|$27$|$2000$|无|\n|$5$|$34$|$5\\times10^5$|无|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9579","tags":["动态规划 DP","贪心","线段树","树状数组","洛谷原创","O2优化","排序","洛谷月赛"],"sample_group":[["2\n3 2\n2 5","7"],["4\n4 7\n10 8\n9 11\n4 2","18"]],"created_at":"2026-03-03 11:09:25"}}