총격전 연출

스티븐 바이트버그는 액션 영화를 전문으로 하는 영화감독이다. 지금은 바이트 마피아 전쟁을 주제로 한 새 영화를 만들고 있다. 바이트버그는 절정 장면인 대규모 총격전을 어떤 모습으로 연출할지 고민하고 있다.

이 장면에는 $n$명의 갱단원이 등장하며, 편의상 1부터 $n$까지 번호를 붙인다. 긴장이 최고조에 이르면 각 갱단원은 무기를 꺼내 다른 갱단원 한 명을 겨눈다. 두 명 이상에게 겨눔을 당하는 갱단원은 없다. 갱단원은 가난하지만 훈련이 잘 되어 있다. 각자 딱 한 발만 쏠 수 있고, 그 한 발은 반드시 명중하며 맞은 사람은 반드시 죽는다.

어느 순간 한 명이 긴장을 견디지 못하고 방아쇠를 당기면서 총격전이 시작된다.

감독은 갱단원이 방아쇠를 당기는 순서를 미리 정해 두었다. 갱단원 $i$는 정확히 시각 $t_i$에 갱단원 $p_i$를 향해 쏘되, 그 시각 이전에 이미 죽었다면 쏘지 못한다. 누군가 자신을 향해 쏘는 바로 그 순간에 갱단원은 죽는다.

감독은 장면이 끝났을 때 몇 명이 살아남는지 알고 싶다. 그런데 바이트버그는 갱단원이 쏘는 순서를 아직 확정하지 못했다. 그래서 가끔 $t_i$ 값 하나를 바꾸라고 지시한다. 그때마다 지금까지의 변경을 모두 반영한 새 순서를 기준으로 생존자가 몇 명인지 알고 싶어 한다.

첫째 줄에 장면에 등장하는 갱단원 수 $n$ ($2 \le n \le 200{,}000$)이 주어진다. 둘째 줄에 $n$개의 정수 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i \ne i$, $i \ne j$이면 $p_i \ne p_j$)이 주어진다. 갱단원 $i$가 갱단원 $p_i$를 겨눈다는 뜻이다.

셋째 줄에 $n$개의 정수 $u_1, u_2, \dots, u_n$ ($1 \le u_i \le 10^9$)이 주어진다. 처음 사격 순서를 나타내며, $t_i$의 초깃값은 $u_i$이다.

넷째 줄에 바이트버그가 계획한 $t_1, \dots, t_n$의 변경 횟수 $q$ ($0 \le q \le 200{,}000$)가 주어진다. 다음 $q$개 줄에 변경 내용이 주어진다. 그중 $i$번째 줄에는 두 정수 $k_i$와 $v_i$ ($1 \le k_i \le n$, $1 \le v_i \le 10^9$)가 주어지며, $i$번째 변경은 $t_{k_i}$를 $v_i$로 바꾸는 것이다. $u_1, u_2, \dots, u_n, v_1, v_2, \dots, v_q$는 모두 서로 다르다.

정확히 $q+1$개의 줄을 출력한다. 첫째 줄에는 처음 사격 순서대로 진행했을 때 살아남는 갱단원 수를 출력한다. 그다음 $q$개 줄 중 $i$번째 줄에는 첫 번째부터 $i$번째까지의 변경을 모두 적용한 뒤의 $t_1, \dots, t_n$을 기준으로 진행했을 때 살아남는 갱단원 수를 출력한다.