King

Time limit2sMemory limit128 MB

Summary

N elves each target a dwarf; elves enter one at a time and slide clockwise to the next free spot. Choose the entry order to maximize elven wins.

Level: Hard8 of 10
Topics: Greedy, Sorting, Union-find, Implementation
Solved: No attempts yet

Problem

Young ruler Mirko has declared himself king of the dwarves. Slavko felt threatened by the news and declared himself king of the elves. There cannot be two kings in one land, so the two of them decided to settle the question of power for good.

Slavko takes the $N$ strongest elves of his kingdom, numbered $1$ through $N$ , to Mirko's castle. In the castle hall the $N$ strongest dwarves are sitting in a circle, numbered $1$ through $N$ clockwise.

When the elves entered, Mirko gave each of them a number $A_i$ , the number of the dwarf that elf will fight. He did not make sure that every elf gets a different opponent, and a terrible fight broke out.

The two rulers decided to solve the problem this way.

Slavko sends his elves into the hall one at a time, in an order of his own choosing. The next elf enters only after the previous one has found a seat.
Elf $k$ first walks up to dwarf $A_k$ . If no elf is sitting beside that dwarf, elf $k$ sits there. Otherwise elf $k$ keeps walking clockwise from dwarf to dwarf until it finds a dwarf with no elf beside it.

The resulting $N$ pairs of elves and dwarves then compete in armwrestling, and the stronger one always wins.

Slavko has studied every fighter and knows how strong each one is. He wants to send the elves into the hall in the order that gives his side the most victories once everyone is seated.

Compute the largest number of duels the elves can win.

Input

The first line contains the integer $N$ ( $1 \le N \le 5 \times 10^5$ ).

The second line contains $N$ integers $A_1, A_2, \dots, A_N$ , the opponents chosen by Mirko ( $1 \le A_i \le N$ ).

The third line contains $N$ integers $P_1, P_2, \dots, P_N$ , the strengths of the dwarves ( $1 \le P_i \le 10^9$ ).

The fourth line contains $N$ integers $V_1, V_2, \dots, V_N$ , the strengths of the elves ( $1 \le V_i \le 10^9$ ).

All $2N$ strengths in the input are distinct.

Output

Print the largest number of duels the elves can win.

Note

In the first example Slavko can send the elves in the order $3, 2, 1$ . Elf $3$ sits beside dwarf $3$ , elf $2$ moves one seat clockwise and sits beside dwarf $1$ , and elf $1$ sits beside dwarf $2$ . Elves $1$ and $2$ win their duels and elf $3$ loses.

Examples3

Example 1
Input
```
3
2 3 3
4 1 10
2 7 3
```
Expected output
```
2
```
Example 2
Input
```
4
3 1 3 3
5 8 7 10
4 1 2 6
```
Expected output
```
1
```
Example 3
Input
```
3
1 2 3
8 4 3
9 2 6
```
Expected output
```
2
```