You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

矮人国和精灵国即将爆发战争！精灵王 Slavko 将 $n$ 个精灵编号为 $1\dots n$。矮人王 Mirko 则让 $n$ 个矮人围成一个圆环，从某个矮人开始顺时针编号为 $1\dots n$。

接下来，Mirko 将为每个精灵分配一个数字 $a_i$，表示将与它们决斗的矮人的编号。然而，由于他的粗心，不同精灵分配到的数字可能是相同的。

为了决斗的公平，双方决定：

1. Slavko 选出一位尚未确定对手的精灵，设其编号为 $i$。
2. 若编号为 $a_i$ 的矮人尚未确定对手，则将其作为这位精灵的对手。否则，从编号为 $a_i$ 的矮人开始，选择沿圆环顺时针方向第一个尚未确定对手的矮人作为这位精灵的对手。
3. 重复以上步骤，直到所有矮人及精灵都确定了对手。

Slavko 收集了所有矮人及精灵的力量值。决斗时，力量值大的一方总是获胜。他想知道，通过规划选择精灵的顺序，最多能有多少精灵在决斗中获胜。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_i$。

第三行 $n$ 个整数 $p_i$，表示编号为 $i$ 的矮人的力量值。

第四行 $n$ 个整数 $v_i$，表示编号为 $i$ 的精灵的力量值。

输出格式

一行，一个整数，表示最多能有多少精灵在决斗中获胜。

3
2 3 3
4 1 10
2 7 3 

2 

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

1 

3
1 2 3
8 4 3
9 2 6 

2 

提示

样例 1 解释

Slavko 以 $3,2,1$ 的顺序选择精灵。

这样，编号为 $1,2,3$ 的精灵的对手编号分别为 $2,1,3$。

编号为 $1,2$ 的精灵将在决斗中获胜。

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le 5\times 10^5$，$1\le a_i\le n$，$1\le p_i,v_i\le 10^9$。

说明

题目译自 COCI2016-2017 CONTEST #1 T5 Kralj。