Problem
Mirko menjadi CEO sebuah syarikat besar. Syarikat itu menggaji N orang, yang bernombor dari 1 hingga N, dan Mirko sendiri mempunyai nombor 1. Semua pekerja, kecuali Mirko, mempunyai bos. Seorang bos boleh mempunyai beberapa orang bawahan, tetapi tidak lebih daripada seorang bos.
Apabila Mirko menerima tugasan daripada pelabur, dia menyerahkannya kepada orang bawahannya yang mempunyai bilangan paling rendah. Orang bawahan itu juga meneruskannya kepada orang bawahannya yang bernombor paling rendah, dan seterusnya, sehingga pekerjaan itu berpindah kepada pekerja yang tidak bernasib baik tanpa orang bawahan untuk menyelesaikannya.
Pekerja itu mendapat 1 syiling, bosnya mendapat 2 syiling, bos bos itu mendapat 3 syiling, dan seterusnya. Kemudian orang yang benar-benar melakukan kerja itu menyedari betapa tidak adilnya sistem kapitalis ini dan berhenti kerja.
Mirko menerima tugasan sehingga hanya seorang pekerja kekal dalam perbadanan itu — Mirko sendiri. Kemudian dia menyelesaikan tugas ini, menerima 1 syiling dan meninggalkan perbadanan itu.
Dia tertanya-tanya berapa banyak syiling yang diterima setiap bekas pekerja. Bantu dia dengan ini.
Input:
Baris pertama mengandungi satu nombor asli N (1 ≤ N ≤ 2·10
5) — bilangan pekerja syarikat. Baris seterusnya mengandungi nombor N-1 a
2, a
3, ... a
n (1 ≤ a
i <i), a
i — nombor ketua pekerja ke-i.
Output:
Cetak nombor N, nombor ke-i harus menunjukkan bilangan syiling yang diterima oleh pekerja ke-i.
Contoh:
| Input |
Output |
3
1 1
| 5 1 1 |
5
1 2 2 4
| 13 8 1 3 1 |
Penjelasan:
Berikut ialah penerangan bagi contoh kedua.
Mirko memberikan tugas pertama kepada pekerja 2, yang menyerahkannya kepada pekerja 3, yang menyelesaikan tugas itu. Oleh itu, pekerja 3 menerima satu syiling, pekerja 2 — dua syiling, dan pekerja 1, Mirko sendiri, — tiga syiling. Selepas itu, pekerja 3 berhenti.
Mirko memberikan tugas kedua kepada pekerja 2, yang menyerahkannya kepada pekerja 4, yang segera menyerahkan tugas kepada pekerja 5, yang menyelesaikan tugas itu. Selepas itu, pekerja 5 menerima satu syiling, pekerja 4 — dua syiling, pekerja 2 — tiga syiling, dan Mirko — empat syiling. Pekerja 5 berhenti.
Selepas menyelesaikan tugasan ketiga, pekerja 4 menerima satu syiling, pekerja 2 — dua syiling, dan Mirko — tiga syiling, selepas itu pekerja 4 berhenti.
Selepas menyelesaikan tugasan keempat, pekerja 2 menerima satu syiling, dan Mirko — dua syiling, selepas itu pekerja kedua berhenti.
Akhirnya, tugas kelima dilakukan oleh Mirko sendiri, menerima satu syiling untuk ini, selepas itu proses berhenti.
Secara keseluruhan, Mirko menerima 13 syiling, seorang pekerja 2 — 8 syiling, pekerja 4 — 3 syiling, dan pekerja 3 dan 5 — satu syiling.