Description

Russian nesting dolls are wooden figurines of strictly increasing sizes that can be nested inside one another. Each figurine can be put into a larger figurine, and can itself contain a smaller figurine. At most one figurine can be directly nested inside any figurine, but that inner figurine can itself contain another, and so on.

Given $n$ figurines with distinct sizes, they are numbered $1$ to $n$ in increasing order of size. If figurine $a$ is directly nested inside figurine $b$, then we say $b$ is the parent of $a$. If a figurine has no parent, we say it is free. A nesting configuration can be represented by specifying the parent of each figurine.

In each step, you may perform exactly one of the following two operations:

1. Take a free figurine and directly place it into a larger figurine that currently contains nothing.
2. Choose a figurine that is not free (i.e., has a parent) and remove it from its parent.

Given the initial configuration, compute the minimum number of steps to reach the target configuration.

Input Format

The first line contains a positive integer $n(1 \le n \le 100000)$, the number of figurines.

The second line contains $n$ integers $p_1,p_2,...,p_n(0 \le p_i \le n)$, giving the parent of each figurine in the initial configuration, where $0$ denotes a free figurine.

The third line contains $n$ integers $q_1,q_2,...,q_n(0 \le q_i \le n)$, giving the parent of each figurine in the target configuration, where $0$ denotes a free figurine.

The input guarantees that both the initial and the target configurations are valid.

Output Format

Output a single integer, the minimum number of operations.

7
3 5 4 0 7 0 0
3 5 0 6 7 0 0

2

Hint

Translated by ChatGPT 5