Підрахунок підвищень#10553
Корови знову спробували створити стартап-компанію, очевидно забувши минулий досвід, який показав, що з корів виходять жахливі менеджери!
Корови, зручно пронумеровані числами 1, \ldots, n, організують компанію у вигляді дерева, де корова є президентом (коренем дерева). У кожної корови, крім президента, є єдиний менеджер (її «батько» в дереві). Кожна корова має унікальний рейтинг професіоналізму , який характеризує, наскільки добре вона справляється зі своєю роботою. Якщо корова є предком (наприклад, менеджером, менеджером менеджера або ще вищого рівня) корови , то ми називаємо корову підлеглою корови .
На жаль, корови виявили, що менеджери часто мають нижчий рейтинг професіоналізму, ніж деякі з їхніх підлеглих. У таких випадках менеджеру варто розглянути можливість підвищення деяких зі своїх підлеглих. Ваше завдання — допомогти коровам визначити, коли виникає така ситуація. Для кожної корови підрахуйте кількість її підлеглих , для яких виконується p(j) \u003e p(i).
У першому рядку міститься число n~(1 \le n \le 10^5). У наступних рядках містяться рейтинги професіоналізму p(1), \ldots, p(n) корів. Усі рейтинги професіоналізму різні і є цілими числами в діапазоні від до 10^9.
У наступних n - 1 рядках описується менеджер (батько) кожної з корів 2, \ldots, n. Нагадаємо, що корова не має менеджера, оскільки вона є президентом.
Виведіть рядків. У -му рядку виведіть кількість підлеглих корови , рейтинг професіоналізму яких вищий, ніж у корови .
Приклад 1