Problem
Mirko trở thành CEO của một tập đoàn lớn. Công ty sử dụng N người, những người được đánh số từ 1 đến N và bản thân Mirko có số 1. Tất cả nhân viên, ngoại trừ Mirko, đều có một ông chủ. Một ông chủ có thể có nhiều cấp dưới, nhưng không được nhiều hơn một ông chủ.
Khi Mirko nhận được nhiệm vụ từ các nhà đầu tư, anh ấy sẽ giao nó cho cấp dưới của mình với số lượng thấp nhất. Cấp dưới đó cũng chuyển công việc đó cho cấp dưới có số thứ tự thấp nhất của anh ta, v.v., cho đến khi công việc được chuyển cho một công nhân kém may mắn không có cấp dưới nào để hoàn thành.
Người công nhân đó nhận được 1 đồng xu, ông chủ của anh ta nhận được 2 đồng xu, ông chủ của ông chủ đó nhận được 3 đồng xu, v.v. Sau đó, người thực sự làm công việc nhận ra hệ thống tư bản này bất công như thế nào và bỏ việc.
Mirko nhận nhiệm vụ cho đến khi chỉ còn một nhân viên trong công ty — Bản thân Mirko. Sau đó, anh ta hoàn thành nhiệm vụ này, nhận được 1 đồng xu và rời khỏi công ty.
Anh tự hỏi tổng cộng mỗi nhân viên cũ nhận được bao nhiêu xu. Giúp anh ấy với điều này.
Đầu vào:
Dòng đầu tiên chứa 1 số tự nhiên N (1 ≤ N ≤ 2·10
5) — số lượng nhân viên của công ty. Dòng tiếp theo chứa N-1 số a
2, a
3, ... a
n (1 ≤ a
i <i), a
i — số của người đứng đầu nhân viên thứ i.
Đầu ra:
In ra N số, số thứ i sẽ cho biết nhân viên thứ i đã nhận được bao nhiêu xu.
Ví dụ:
| Đầu vào |
Đầu ra |
3
1 1
| 5 1 1 |
5
1 2 2 4
| 13 8 1 3 1 |
Giải thích:
Sau đây là mô tả về ví dụ thứ hai.
Mirko giao nhiệm vụ đầu tiên cho công nhân 2, người này chuyển nó cho công nhân 3, người này đã hoàn thành nhiệm vụ. Do đó, công nhân 3 nhận được một đồng xu, công nhân 2 — hai đồng xu và công nhân 1, chính Mirko, — ba đồng xu. Sau đó, nhân viên thứ 3 nghỉ việc.
Mirko giao nhiệm vụ thứ hai cho công nhân 2, người này chuyển nó cho công nhân 4, người này ngay lập tức chuyển nhiệm vụ cho công nhân 5, người này đã hoàn thành nhiệm vụ. Sau đó, công nhân 5 nhận được một đồng xu, công nhân 4 — hai đồng xu, công nhân 2 — ba đồng xu và Mirko — bốn đồng xu. 5 nhân viên nghỉ việc.
Sau khi hoàn thành nhiệm vụ thứ ba, công nhân 4 nhận được một đồng xu, công nhân 2 — hai đồng xu và Mirko — ba đồng xu, sau đó nhân viên thứ 4 nghỉ việc.
Sau khi hoàn thành nhiệm vụ thứ tư, công nhân 2 nhận được một đồng xu và Mirko — hai đồng xu, sau đó nhân viên thứ hai nghỉ việc.
Cuối cùng, nhiệm vụ thứ năm do chính Mirko thực hiện, nhận được một đồng xu cho việc này, sau đó quá trình dừng lại.
Tổng cộng, Mirko nhận được 13 xu, một nhân viên 2 — 8 xu, công nhân 4 — 3 xu và công nhân 3 và 5 — một đồng xu.