The Staging

Steven Byteberg is a movie director who specializes in action movies. He is now working on a new movie about the Byteonian Mafia wars. Byteberg wonders what the climax of the movie, a spectacular exchange of gunfire, should look like.

$n$ gangsters take part in this scene. For simplicity they are numbered from 1 to $n$. When the tension reaches its peak, every gangster draws his weapon and takes aim at another gangster. Nobody is aimed at by more than one gangster. The gangsters are poor but well trained: each of them can shoot only once, and that shot is always accurate and always deadly.

At some point one of the thugs cannot stand the tension any longer, and the shooting starts.

The director has fixed the order in which the gangsters pull their triggers. Gangster $i$ shoots at gangster $p_i$ at exactly the moment $t_i$, unless gangster $i$ has already been killed by then. A gangster is killed at exactly the moment someone shoots at him.

The director wants to know how many gangsters are alive at the end of the scene. Byteberg is not yet sure about the order in which the gangsters shoot. From time to time he orders one of the values $t_i$ to be changed. After every such change he wants to know how many gangsters survive under the new order, taking into account all changes made so far.

The first line contains one integer $n$ ($2 \le n \le 200{,}000$), the number of gangsters in the scene. The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i \ne i$, and $p_i \ne p_j$ for $i \ne j$), where gangster $i$ aims at gangster $p_i$.

The third line contains $n$ integers $u_1, u_2, \dots, u_n$ ($1 \le u_i \le 10^9$) describing the initial shooting order: the initial value of $t_i$ is $u_i$.

The fourth line contains one integer $q$ ($0 \le q \le 200{,}000$), the number of changes to $t_1, \dots, t_n$ that Byteberg plans. Each of the next $q$ lines describes one change. The $i$-th of these lines contains two integers $k_i$ and $v_i$ ($1 \le k_i \le n$, $1 \le v_i \le 10^9$), meaning that the $i$-th change sets $t_{k_i}$ to $v_i$. The numbers $u_1, u_2, \dots, u_n, v_1, v_2, \dots, v_q$ are pairwise distinct.

Print exactly $q+1$ lines. The first line contains the number of gangsters who survive the shooting under the initial order. The $i$-th of the following $q$ lines contains the number of gangsters who survive when the shooting order is given by $t_1, \dots, t_n$ after the first $i$ changes have been applied.