Коровы, последовательно пронумерованные \(1 \ldots N\) (\(1 \leq N \leq 100,000\)),
организовали компанию в виде дерева, где корова 1 - президент (корень дерева).
Каждая корова, кроме президента, имеет ровно одного менеджера (её родитель в дереве).
Каждая корова \(i\) имеет различный професиональный рейтинг \(p(i)\), который описывает
насколько хорошо она делает свою работу. Если корова \(i\) есть менеджер коровы \(j\),
то мы говорим, что корова \(j\) подчиняется корове \(i\).
К несчастью коровы обнаружили что часто бывает так, что менеджер имеет меньший
уровень профессиональности, чем некоторые из его подчинённых. В этом случае менеджер
должен рассмотреть продвижение этих подчинённых. Ваша задача - помочь коровам
узнать, когда это случается. Для каждой коровы \(i\) в компании вычислите количество
подчинённых \(j\) таких, что \(p(j) > p(i)\).
ФОРМАТ ВВОДА (файл promote.in):
Первая строка ввода содержит
\(N\).
Следующие \(N\) строк ввода содержат рейтинги профессиональности коров \(p(1) \ldots p(N)\).
Все числа - различные целые в интервале \(1 \ldots 1,000,000,000\).
Следующие \(N-1\) строк описывают менеджера (родителя) для коров \(2 \ldots N\).
Напомним что у коровы 1 нет менеджера, поскольку она президент.
ФОРМАТ ВЫВОДА (файл promote.out):
Выведите \(N\) строк. \(i\)-ая строка вывода должна говорить количество подчинённых коровы \(i\)
с рейтингом профессиональности большим чем у коровы \(i\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
804289384
846930887
681692778
714636916
957747794
1
1
2
3
|
2
0
1
0
0
|