题目背景

电梯是一个可以让人充分思考的空间。

题目描述

给定两个长度为 $n$ 的数组 $a,b$。我们称序列 $p$ 是满足条件的，设 $p$ 的长度为 $m$，当且仅当：

• $p_1=1$；
• 对于所有的 $1\le i
• 对于所有的 $1\le k\le n$，都存在一个有序数对 $(i,j)$，满足 $1 \le i < j \le m$ 且 $p_i=a_k$，$p_j=b_k$。

你需要输出所有满足条件的序列 $p$ 中，$p$ 的长度的最小值。

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，第 $i$ 行两个整数 $a_i,b_i$。

输出格式

一个整数，表示所有满足条件的序列 $p$ 中，$p$ 的长度的最小值。

样例 1 输入

2
3 2
2 5

样例 1 输出

7

样例 1 解释

序列 $p$ 的长度的最小值为 $7$，此时的序列 $p$ 为 $\{1,2,3,2,3,4,5\}$。

样例 2 输入

4
4 7
10 8
9 11
4 2

样例 2 输出

18

数据范围

对于所有数据，$1 \le n \le 5\times10^5$，$1 \le a_i,b_i \le 10^9$，保证 $a_i \neq b_i$。

本题采用捆绑测试。