#P4756. [Usaco2017 Jan]Promotion Counting

    ID: 3876 传统题 1000ms 128MiB 尝试: 662 已通过: 317 难度: 4 上传者: 标签>难度分类普及+/提高-树算法DFS 序子树转区间离线与分治离线查询查询排序数据结构树状数组CF1600

[Usaco2017 Jan]Promotion Counting

Description

The cows have once again tried to form a startup company, failing to remember from past experience that cows make terrible managers! The cows, conveniently numbered 1∼N1\sim N (1≤N≤100,0001\leq N\leq 100,000), organize the company as a tree, with cow 11 as the president (the root of the tree). Each cow except the president has a single manager (its "parent" in the tree). Each cow ii has a distinct proficiency rating, pip_i, which describes how good she is at her job. If cow ii is an ancestor (e.g. a manager of a manager of a manager) of cow jj, then we say jj is a subordinate of ii.

Unfortunately, the cows find that it is often the case that a manager has less proficiency than several of her subordinates, in which case the manager should consider promoting some of her subordinates. Your task is to help the cows figure out when this is happening. For each cow ii in the company, please count the number of subordinates jj where pj>pip_j > p_i.

Format

Input

The first line of input contains NN.

The next NN lines of input contain the proficiency ratings p1∼pNp_1\sim p_N for the cows. Each is a distinct integer in the range 1∼1,000,000,0001\sim 1,000,000,000.

The next N−1N-1 lines describe the manager (parent) for cows 2∼N2\sim N.

Recall that cow 11 has no manager, being the president.

Output

Please print NN lines of output. The ith line of output should tell the number of subordinates of cow ii with higher proficiency than cow ii.

Samples

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3
2
0
1
0
0