Eric is jumping on a series of ~N~ stone pillars. The ~i^{th}~ pillar has a height of ~h_i~ and Eric can only jump to this pillar from pillar ~p_i~, ~(p_i < i)~. Eric starts at pillar ~1~ and will be happy if he can jump on a sequence of pillars of strictly increasing height. In other words, Eric wants a sequence of indices, ~x_1, x_2, \dots, x_k~ ~(1 \le x_1 < x_2 < \dots < x_k \le N)~, ~x_1=1~ and for all ~1 < j \le k~, ~h_{x_{j-1}} < h_{x_j}~ and ~x_{j-1} = p_{x_j}~. Andy is watching Eric jump and decides to help him out. Andy can change the height of any pillar to any value (yes, he can make pillars negative height) with no cost at all. If Eric wants to jump to pillar ~i~, what is the minimal number of changes Andy needs to make so that Eric will be happy when jumping?

Input Specification

The first line contains one integer ~N~ ~(1 \leq N \leq 2\cdot10^5)~, the number of pillars.

The second line contains ~N~ space separated integers, ~h_i~ ~(1 \leq h_i \leq 10^9)~, the heights of the pillars.

The third line contains ~N-1~ space separated integers, ~p_2,p_3,\dots,p_N~, ~(p_i < i)~ the pillar that Eric needs to jump from to reach pillar ~i~. Note that since Eric starts from pillar ~1~, ~p_1~ does not have a value.

Output Specification

Output ~N~ space separated integers, the minimal amount of changes Andy needs to make so Eric can jump to pillar ~i~.

Subtasks

Subtask 1 [50%]

~1 \leq N \leq 5000~

Subtask 2 [50%]

No further constraints.

Sample Input

10
2 5 6 5 2 1 7 9 7 2
1 2 2 4 2 1 7 1 2

Sample Output

0 0 0 1 2 1 0 0 0 1

Sample Explanation

Consider the path to pillar ~5~. The path is ~1 \rightarrow 2 \rightarrow 4 \rightarrow 5~. The original heights of the pillars in this path are ~2, 5, 5, 2~. For Eric to be happy, Andy must change at least ~2~ pillars. For example, he could change the heights of pillars ~4~ and ~5~ to become height ~7~ and ~100000~. The sequence of heights would become ~2, 5, 7, 100000~ which is strictly increasing.