班级里有 $N$ 名学生。每名学生根据其当前的班级排名被分配了一个从 $0$ 到 $N - 1$ 的编号。也就是说，学生 $i$（对于所有 $0 \le i \le N - 1$）当前的班级排名为 $i$。其中排名 $0$ 为最好，排名 $N-1$ 为最差。

最近举行了英语和数学考试。学生 $i$（对于所有 $0 \le i \le N - 1$）在英语考试中的排名为 $A[i]$，在数学考试中的排名为 $B[i]$。$A$ 和 $B$ 均为长度为 $N$ 的排列。

什么是长度为 $N$ 的排列？ 在本题中，长度为 $N$ 的排列 $P$ 是一个长度为 $N$ 的数组，满足对于所有 $0 \leq i \leq N-1$ 有 $0 \leq P[i] \leq N-1$，且对于所有 $0 \leq i < j \leq N-1$ 有 $P[i] \neq P[j]$。例如，$[2,1,0]$ 是长度为 $3$ 的排列，但 $[1,2,3]$ 和 $[2,0,2]$ 不是长度为 $3$ 的排列。

老师想要重新对学生进行排名。新的排名可以用一个排列 $P$ 来表示。

对于每名学生 $i$，新的班级排名必须满足以下条件中的至少一个：

• 对于所有满足 $P[j] < P[i]$ 的学生 $j$，学生 $j$ 在英语考试中比学生 $i$ 优秀（即 $A[j] < A[i]$），或者
• 对于所有满足 $P[j] < P[i]$ 的学生 $j$，学生 $j$ 在数学考试中比学生 $i$ 优秀（即 $B[j] < B[i]$）。

警告：该条件仅适用于满足 $P[j] < P[i]$ 的学生 $j$。对于满足 $P[j] \geq P[i]$ 的学生 $j$ 没有限制。对于每名学生 $i$，在评估条件是否满足时，他们必须首先选择一门科目，并根据该科目评估所有学生 $j$。对于给定的学生 $i$，在评估条件时，所有学生 $j$ 必须基于同一门科目进行比较。在评估学生 $i$ 的条件时，不能中途切换科目。

新班级排名的不满度定义为所有学生中排名下降幅度的最大值。换句话说，不满度是 $P[i] - i$（对于所有 $0 \leq i \leq N - 1$）的最大值。

警告：不满度是 $P[i] - i$ 的最大值，$i - P[i]$ 的值不影响不满度。

求新班级排名的最小可能不满度。

实现细节

你需要实现以下函数：

int minimum_dissatisfaction(int N, std::vector<int> A, std::vector<int> B)

• $N$：学生人数。
• $A$：一个长度为 $N$ 的数组，描述英语考试的排名。
• $B$：一个长度为 $N$ 的数组，描述数学考试的排名。
• 该函数应返回新班级排名的最小不满度。
• 该函数将被调用恰好一次。

数据范围

• $1 \leq N \leq 5\;000\;000$。
• $0 \leq A[i], B[i] \leq N - 1$，对于所有 $0 \leq i \leq N - 1$。
• $A[i] \neq A[j]$，对于所有 $0 \leq i < j \leq N - 1$。
• $B[i] \neq B[j]$，对于所有 $0 \leq i < j \leq N - 1$。

子任务

1. (3 分) $N \leq 8$。
2. (4 分) $N \leq 20$。
3. (13 分) $N \leq 500$。
4. (12 分) $N \leq 3000$，$A[i] + B[i] = N - 1$，对于所有 $0 \leq i \leq N - 1$。
5. (19 分) $N \leq 3000$。
6. (15 分) $N \leq 100\;000$，$A[i] + B[i] = N - 1$，对于所有 $0 \leq i \leq N - 1$。
7. (17 分) $N \leq 100\;000$。
8. (17 分) 无额外限制。

说明：对于子任务 8，仅评测程序本身就保证会消耗 3000ms 时间限制中的 1500ms。

样例

考虑以下调用：

minimum_dissatisfaction(5, [3, 0, 4, 1, 2], [0, 3, 2, 4, 1])

在此示例中，一种分配新排名的方式是 $P = [0, 2, 3, 4, 1]$。

考虑学生 $1$，其 $P[1] = 2$。所有满足 $P[j] < P[1]$ 的学生 $j$ 在数学考试中的排名都比学生 $1$ 好，因此该学生满足班级排名条件。

接下来，考虑学生 $2$，其 $P[2] = 3$。所有满足 $P[j] < P[2]$ 的学生 $j$ 在英语考试中的排名都比学生 $2$ 好，因此该学生也满足班级排名条件。

可以验证所有其他学生也都满足班级排名条件。

新排名的不满度为 $1$。不存在不满度更低的新排名，因此该函数应返回 $1$。

样例评测程序

输入格式：

N
A[0] A[1] ... A[N - 1]
B[0] B[1] ... B[N - 1]

输出格式：

一个代表 minimum_dissatisfaction 返回值的整数。