Đàn bò lại một lần nữa thử thành lập công ty khởi nghiệp, vì chúng quên mất kinh nghiệm trong quá khứ rằng bò là những nhà quản lý tồi tệ!

Đàn bò, được đánh số thuận tiện từ \(1 \ldots N\) (\(1 \leq N \leq 100\,000\)), tổ chức công ty theo cấu trúc cây, với bò \(1\) là chủ tịch (gốc của cây). Mỗi con bò trừ chủ tịch có đúng một người quản lý ("nút cha" của nó trên cây). Mỗi bò \(i\) có một chỉ số năng lực phân biệt \(p(i)\), mô tả mức độ thành thạo công việc của nó. Nếu bò \(i\) là tổ tiên (chẳng hạn người quản lý của người quản lý của người quản lý) của bò \(j\), ta gọi \(j\) là cấp dưới của \(i\).

Đáng tiếc, đàn bò nhận thấy một người quản lý thường có năng lực thấp hơn một số cấp dưới của mình; khi đó, người quản lý nên cân nhắc đề bạt một vài cấp dưới. Nhiệm vụ của bạn là giúp đàn bò xác định khi nào điều này xảy ra. Với mỗi bò \(i\) trong công ty, hãy đếm số cấp dưới \(j\) thỏa mãn \(p(j)>p(i)\).

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

\(N\) dòng tiếp theo chứa các chỉ số năng lực \(p(1) \ldots p(N)\) của đàn bò. Mỗi chỉ số là một số nguyên phân biệt trong khoảng \(1 \ldots 1\,000\,000\,000\).

\(N-1\) dòng tiếp theo mô tả người quản lý (nút cha) của các con bò \(2 \ldots N\). Nhớ rằng bò \(1\) không có người quản lý vì nó là chủ tịch.

Dữ liệu ra

In \(N\) dòng. Dòng thứ \(i\) cho biết số cấp dưới của bò \(i\) có năng lực cao hơn bò \(i\).

Ví dụ

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3

2
0
1
0
0

Nguồn

USACO 2017 January Contest, Platinum — Promotion Counting. Tác giả đề: Karthik Nair.

https://usaco.org/index.php?page=viewproblem2&cpid=696