시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB52332463.158%

문제

You'd like to design a package manager on your own, and thus you'd like to resolve the dependency problem among packages. If package $A$ depends on package $B$, then we must install package $B$ before package $A$. Likewise, if we'd like to remove package $B$, we also need to remove package $A$. You know the dependency relations among the packages, and you may assume all packages other than package $0$ will rely on exactly one package (package $0$ does not rely on any other packages). There are no cycles in the dependency relation (like $A_1$ depends on $A_2$, $A_2$ depends on $A_3$, …, $A_{m_1}$ depends on $A_m$ but $A_m$ depends on $A_1$), and of course no package depends on itself.

Now you'd like to know how many packages have their status changed upon installing or uninstalling a given package. Notice installing an installed package or uninstalling an uninstalled package will not change the status of any package.

입력

The first line of the input is an integer $n$ representing the number of packages. The packages are numbered beginning with $0$.

The next line has $n-1$ integers separated by a single space, representing the package that package $1, 2, \dots, n-2, n-1$ depends on.

The next line contains an integer $q$ representing the number of queries. In the following $q$ lines, each line contains a query of form install x or uninstall x representing installing or uninstalling package $x$. You need to maintain the status of each package. Initially, all packages are uninstalled. You need to output how many packages will change the status after the step, and then apply the (un)installation.

출력

The output consists of $q$ lines. The $i$-th line is an integer representing the number of packages whose status change at step $i$.

제한

  • $7 ≤ n ≤ 100\,000$
  • $5 ≤ q ≤ 100\,000$    

예제 입력 1

7
0 0 0 1 1 5
5
install 5
install 6
uninstall 1
install 4
uninstall 0

예제 출력 1

3
1
3
2
3

예제 입력 2

10
0 1 2 1 3 0 0 3 2
10
install 0
install 3
uninstall 2
install 7
install 5
install 9
uninstall 9
install 4
install 1
install 9

예제 출력 2

1
3
2
1
3
1
1
1
0
1