#6047. 「雅礼集训 2017 Day10」决斗

内存限制:128 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

Mirko 是侏儒国的国王,Slavko 是精灵国的国王。最近,侏儒国和精灵国进行了一场战争。Slavko 率领着 N 个最强壮的精灵(编号从 1 N )进攻侏儒国,而侏儒国的城堡也由 N 个侏儒(按顺时针方向从 1 N 编号并形成环形)进行防守。

Mirko 为每一个精灵分配了一个侏儒对手 A_i ,表示编号为 i 的精灵要与编号为 A_i 的侏儒进行对决。然而,不久后他就发现,这个方案不能保证每一个侏儒都与唯一一个精灵进行对决。

经过协商,Mirko 和 Slavko 最终定下了如下规则:

  1. Slavko 会按他安排的顺序依次派遣他的精灵进入城堡。一个精灵进入城堡时,上一个进入的精灵必须已经找到了就座的位置并坐下。
  2. 编号为 k 的精灵进入城堡时,会首先靠近编号为 A_k 的侏儒。如果该侏儒旁边的位置没有精灵就座,则该精灵在该位置就座。否则,他将沿着顺时针方向走到下一个侏儒旁的位置,直到他找到一个空位为止。

最终, N 个精灵和侏儒将一一配对,并进行一对一的对决,其中更有力量的一个将会胜出。

Slavko 已经为这场战斗做了充分的准备,他已经知道了每一个精灵和侏儒的力量大小。现在他想直到,合理安排精灵进入城堡的顺序后,他的精灵们最多能赢得多少场对决。

输入格式

第一行一个整数 N
第二行 N 个整数 A_i
第三行 N 个整数,其中第 i 个整数表示第 i 个侏儒的力量值;
第四行 N 个整数,其中第 i 个整数表示第 i 个精灵的力量值。

输出格式

输出一行一个整数,表示精灵们最多赢得多少场对决。

样例

样例输入 1

3
2 3 3
4 1 10
2 7 3

样例输出 1

2

样例输入 2

4
3 1 3 3
5 8 7 10
4 1 2 6

样例输出 2

1

样例输入 3

3
1 2 3
8 4 3
9 2 6

样例输出 3

2

数据范围与提示

对于 40\% 的数据, A_i = 1
对于 100\% 的数据, 1 \leq N \leq 5 \times 10 ^ 5

保证输入的力量值互不相同,且在 [1, 10 ^ 9] 的范围内。