P6288 [COCI 2016/2017 #1] Kralj

A war is about to break out between the Dwarven Kingdom and the Elven Kingdom! The elven king Slavko numbers $n$ elves as $1 \dots n$. The dwarf king Mirko makes $n$ dwarves stand in a circle, and starting from some dwarf, numbers them clockwise as $1 \dots n$. Next, Mirko assigns each elf a number $a_i$, meaning the number of the dwarf that elf will duel. However, due to his carelessness, different elves may be assigned the same number. To make the duels fair, both sides decide: 1. Slavko chooses an elf who has not yet been assigned an opponent, and let its number be $i$. 2. If the dwarf numbered $a_i$ has not yet been assigned an opponent, then that dwarf becomes this elf’s opponent. Otherwise, starting from the dwarf numbered $a_i$, choose the first dwarf clockwise along the circle who has not yet been assigned an opponent as this elf’s opponent. 3. Repeat the above steps until all dwarves and elves have been assigned opponents. Slavko has collected the strength values of all dwarves and elves. In a duel, the side with the greater strength value always wins. He wants to know: by planning the order in which he chooses elves, what is the maximum number of elves that can win their duels?

The first line contains an integer $n$. The second line contains $n$ integers $a_i$. The third line contains $n$ integers $p_i$, where $p_i$ is the strength value of dwarf $i$. The fourth line contains $n$ integers $v_i$, where $v_i$ is the strength value of elf $i$.

One line with one integer, the maximum number of elves that can win their duels.

#### Explanation for Sample 1 Slavko chooses elves in the order $3, 2, 1$. Then, the opponents of elves $1, 2, 3$ are dwarves $2, 1, 3$, respectively. Elves $1$ and $2$ will win their duels. ------------ #### Constraints For $100\%$ of the testdata, $1 \le n \le 5 \times 10^5$, $1 \le a_i \le n$, $1 \le p_i, v_i \le 10^9$. ------------ #### Note **This problem is translated from [COCI2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #1](https://hsin.hr/coci/archive/2016_2017/contest1_tasks.pdf) _T5 Kralj_.** Translated by ChatGPT 5