Problem
Mirko büyük bir şirketin CEO'su oldu. Şirket, 1'den N'ye kadar numaralandırılan N kişiyi istihdam ediyor ve Mirko'nun kendisi 1 numaraya sahip. Mirko dışındaki tüm çalışanların bir patronu var. Bir patronun birkaç astı olabilir, ancak birden fazla patron olamaz.
Mirko, yatırımcılardan bir görev aldığında, onu en düşük numaralı astına devreder. Bu ast aynı zamanda işi en düşük numaralı astına da iletir ve iş, onu tamamlayacak astı olmayan şanssız bir işçiye geçene kadar böyle devam eder.
O işçi 1 jeton alır, patronu 2 jeton alır, o patronun patronu 3 jeton alır, vb. Sonra işi gerçekten yapan, bu kapitalist sistemin ne kadar adaletsiz olduğunu anlar ve işi bırakır.
Mirko, şirkette yalnızca bir çalışan kalana kadar atamaları alır — Mirko'nun kendisi. Daha sonra bu görevi tamamlar, 1 coin alır ve şirketten ayrılır.
Her eski çalışanın toplamda kaç jeton aldığını merak etti. Ona bu konuda yardım et.
Giriş:
İlk satırda bir doğal sayı N (1 ≤ N ≤ 2·10
5) — şirket çalışanlarının sayısı. Sonraki satır N-1 sayıları içerir a
2, a
3, ... a
n (1 ≤ a
i <i), a
i — i. çalışanın başkanının numarası.
Çıktı:
N sayıları yazdırın, i. sayı, i. çalışanın kaç jeton aldığını göstermelidir.
Örnekler:
| Giriş |
Çıktı |
3
1 1
| 5 1 1 |
5
1 2 2 4
| 13 8 1 3 1 |
Açıklamalar:
Aşağıda ikinci örneğin açıklaması yer almaktadır.
Mirko ilk görevi işçi 2'ye verir, o da görevi tamamlayan işçi 3'e verir. Böylece, işçi 3 bir madeni para alır, işçi 2 — iki madeni para ve işçi 1, Mirko'nun kendisi, — üç madeni para. Bundan sonra, çalışan 3 istifa eder.
Mirko ikinci görevi 2. işçiye verir, o da 4. işçiye verir, o da hemen görevi bitiren 5. işçiye verir. Bundan sonra, işçi 5 bir madeni para alır, işçi 4 — iki madeni para, işçi 2 — üç madeni para ve Mirko — dört madeni para. Çalışan 5 istifa ediyor.
Üçüncü görevi tamamladıktan sonra, işçi 4 bir madeni para alır, işçi 2 — iki madeni para ve Mirko — üç madeni para, ardından 4. çalışan istifa eder.
Dördüncü görevi tamamladıktan sonra, 2. işçi bir madeni para alır ve Mirko — iki madeni para, ardından ikinci çalışan işi bırakır.
Son olarak beşinci görev, Mirko'nun kendisi tarafından gerçekleştirilir ve bunun karşılığında bir jeton alınır ve ardından süreç durur.
Toplamda, Mirko 13 madeni para aldı, bir çalışan 2 — 8 madeni para, işçi 4 — 3 madeni para ve işçiler 3 ve 5 — bir madeni para