赛马 - 문제

你正在与你的宿敌进行一场赛马比赛。你和你的宿敌都拥有 $N$ 匹马。这场比赛共有 $N$ 轮，在每一轮中，你的一匹马将与你宿敌的一匹马进行比赛。所有的马都只参赛一次。

你拥有 $N$ 匹马，它们目前排成一排。这一排中的第 $i$ 匹马的速度为 $a_i$。

你的宿敌也将派出 $N$ 匹马，每轮一匹。在每一轮中，速度较高的马将赢得比赛。如果你的马和对手的马速度相同，则你的马获胜。

你确切地知道你的宿敌派出马的顺序。在宿敌的顺序中，第 $i$ 匹马（将在第 $i$ 轮参赛，下标从 0 开始）的速度为 $b_i$。你的宿敌有一个特定的策略，即按照速度非降序的顺序派出马。因此，$b_0 \le b_1 \le b_2 \dots \le b_{n-1}$。

由于你的马目前排成一排，完全重新排列它们需要耗费太多精力。相反，你可以选择马的任意一种循环移位（cyclic shift），并按照该顺序派出它们。我们认为第 $i$（$0 \le i \le N - 1$）种循环移位是指将前 $i$ 匹马移到最后。

如果你选择的顺序能让你赢得所有单场比赛，你就赢得了整场比赛。输出能够让你赢得比赛的循环移位数量！

输入的第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$），表示比赛的轮数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 10^9$），其中 $a_i$ 表示你排在第 $i$ 位的马的速度。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$0 \le b_i \le 10^9$），其中 $b_i$ 表示你的宿敌按顺序派出的第 $i$ 匹马的速度。保证 $b_0 \le b_1 \le b_2 \dots \le b_{n-1}$。

输出一个整数，表示能够让你赢得所有单场马赛的循环移位数量。

3
3 4 7
1 5 6

5
3 6 9 12 15
1 2 3 4 5

QOJ.ac