← 返回题目列表

Codeforces · 1237/B

B. 平衡隧道

中文机器翻译题面 查看原题

考虑单向道路上的隧道。在某一天,编号从 $$$1$$$ 到 $$$n$$$ 的 $$$n$$$ 辆车进出隧道恰好一次。所有的汽车都以匀速通过隧道。

隧道入口处安装了交通执法摄像头。另一个交通执法摄像头安装在隧道出口处。完美平衡。

借助摄像头,我们可以知道汽车进出隧道的顺序。没有两辆车同时驶入或驶出。

交通法规禁止在隧道内超车。如果$$$i$$$ 车在隧道内超越任何其他$$$j$$$ 车,则$$$i$$$ 车必须被罚款。不过,每辆车最多可被罚款一次。

正式地,假设汽车 $$$i$$$ 肯定超过汽车 $$$j$$$,如果汽车 $$$i$$$ 比汽车 $$$j$$$ 晚于汽车 $$$j$$$ 进入隧道,并且比汽车 $$$j$$$ 早于汽车 $$$j$$$ 离开隧道。那么,当且仅当汽车 $$$i$$$ 确实超过了至少另一辆车时,才必须被罚款。

找出必须被罚款的汽车数量。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$),表示汽车数量。

第二行包含$$$n$$$整数$$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$),表示按进入隧道顺序的车辆ID。所有 $$$a_i$$$ 都是成对不同的。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$),表示按出隧道顺序排列的车辆 ID。所有 $$$b_i$$$ 都是成对不同的。

输出

输出被罚款的汽车数量。

示例

输入 #1

5
3 5 2 1 4
4 3 2 5 1

输出 #1

2

输入 #2

7
5 2 3 6 7 1 4
2 3 6 7 1 4 5

输出 #2

6

输入 #3

2
1 2
1 2

输出 #3

0

注意

第一个示例如下所示:

汽车 $$$2$$$ 肯定超过了汽车 $$$5$$$,而汽车 $$$4$$$ 肯定超过了汽车 $$$1$$$、$$$2$$$、$$$3$$$ 和 $$$5$$$。汽车 $$$2$$$ 和 $$$4$$$ 必须被罚款。

在第二个示例中,$$$5$$$ 肯定被所有其他汽车超越。

在第三个示例中,任何车辆都不得被罚款。