Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types

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 second 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.


Subtask 1 [50%]

1 \leq N \leq 5000

Subtask 2 [50%]

No further constraints.

Sample Input

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.


There are no comments at the moment.