题目描述

班级里有 $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$ 的排列。

:::info[什么是长度为 $N$ 的排列？]{open} 在本题中，长度为 $N$ 的排列 $P$ 是一个长度为 $N$ 的数组，满足对于所有 $0 \le i \le N - 1$ 有 $0 \le P[i] \le N - 1$ ，且对于所有 $0 \le i < j \le N - 1$ 有 $P[i] \ne 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]$ ）。

:::warning[警告]{open} 该条件仅适用于满足 $P[j] < P[i]$ 的 $j$ 。对于满足 $P[j] \ge P[i]$ 的 $j$ 则没有任何限制。

对于每位学生 $i$ ，在评估其是否满足条件时，必须首先选择一门学科，然后用该学科与所有对应的学生 $j$ 进行比较。对于同一个 $i$ ，所有不同的 $j$ 必须在同一门学科上优于学生 $i$ 。你不能在为学生 $i$ 评估条件时中途切换学科。 :::

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

:::warning[警告]{open}

不满意度是 $P[i] - i$ 的最大值， $i - P[i]$ 的值不会影响不满意度的计算。 :::

在所有可能的新排名中，请找出最小可能的不满意度。

实现详情

你需要实现以下函数：

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

• $N$ ：学生人数。
• $A$ ：一个长度为 $N$ 的数组，表示中文考试的排名。
• $B$ ：一个长度为 $N$ 的数组，表示数学考试的排名。
• 此函数应返回新班级排名的最小不满意度。
• 此函数在每个测试数据中恰好被调用一次。

输入格式

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

输出格式

一个整数，表示 minimum_dissatisfaction 的返回值。

提示

样例

考虑以下函数调用：

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

约束

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

子任务

1. （$3$ 分） $N \le 8$ 。
2. （$4$ 分） $N \le 20$ 。
3. （$13$ 分） $N \le 500$ 。
4. （$12$ 分） $N \le 3000$ ，且对于所有 $0 \le i \le N - 1$ 有 $A[i] + B[i] = N - 1$ 。
5. （$19$ 分） $N \le 3000$ 。
6. （$15$ 分） $N \le 100\ 000$ ，且对于所有 $0 \le i \le N - 1$ 有 $A[i] + B[i] = N - 1$ 。
7. （$17$ 分） $N \le 100\ 000$ 。
8. （$17$ 分）没有额外的约束。

注：对于子任务 $8$ ，仅评测程序就保证会占用 $3000$ 毫秒时间限制中的 $1500$ 毫秒。