Коровы, последовательно пронумерованные 1 .. n, организовали компанию в виде дерева, где корова 1 - президент (корень дерева). Каждая корова, кроме президента, имеет ровно одного менеджера (её родитель в дереве). Каждая корова i имеет различный професиональный рейтинг p(i), который описывает насколько хорошо она делает свою работу. Если корова i есть менеджер коровы j, то мы говорим, что корова j подчиняется корове i.

К несчастью коровы обнаружили что часто бывает так, что менеджер имеет меньший уровень профессиональности, чем некоторые из его подчинённых. В этом случае менеджер должен рассмотреть продвижение этих подчинённых. Ваша задача - помочь коровам узнать, когда это случается. Для каждой коровы i в компании вычислите количество подчинённых j таких, что p(j) > p(i).

Входные данные

Первая строка содержит число n (1 ≤ n ≤ 105). Следующие n строк содержат рейтинги профессиональности коров p(1) .. p(n). Все числа - различные целые в интервале 1 .. 109.

Следующие n − 1 строк описывают менеджера (родителя) для коров 2 .. n. Напомним что у коровы 1 нет менеджера, поскольку она президент.

Выходные данные

Выведите n строк. i-ая строка вывода должна говорить количество подчинённых коровы i с рейтингом профессиональности большим чем у коровы i.