Masala D

Zarif katta korporatsiya bosh direktori bo‘ldi. Ushbu korporatsiya $N$ nafar xodimdan iborat bo‘lib, ular $1$ dan $N$ gacha raqamlangan, bunda $i-$ ishchining yuvoshlik darajasi $i$ ga teng, Zarif esa $1$-raqamga ega. Korporatsiya tuzilishi shundayki, Zarifdan tashqari har bir xodimning o‘z rahbari bor va biz ushbu xodimni o‘sha rahbarning yordamchisi deb ataymiz. Har bir rahbarga bir nechta yordamchi bo‘lishi mumkin, lekin ular ham o‘z navbatida o‘z rahbariga hisob beradi. Mirko esa piramidaning eng yuqori pog‘onasida turgan holda rahbariga ega emas, lekin uning ko‘plab yordamchilari bor.

Investorlar Zarifga topshiriq berganida, u uni eng yuvosh yordamchisiga uzatadi. Keyin bu yordamchi o‘zining eng yuvosh yordamchisiga topshiriqni uzatishni davom ettiradi va jarayon, yordamchisi bo‘lmagan (ya’ni “baxtsiz”) xodimga yetguncha davom etadi. Topshiriq bajarilgandan so'ng haq to‘lash sxemasi quyidagicha:

• Topshiriqni bajaruvchi xodimga $1$ tanga to‘lanadi,
• uning rahbariga $2$ tanga,
• shu rahbarning rahbariga $3$ tanga,
• … va shu tariqa Zarifgacha davom etadi; Zarif esa ushbu ketma‑ketlikdagi odamlar soniga teng tanga oladi.

Topshiriq bajarib bo‘lingach, uni amalga oshirgan xodim tizim adolatsizligini anglab, ishidan voz kechadi. Keyingi topshiriqni bajarishda korporatsiyada bir kishi kam qolgan bo‘ladi, shuning uchun to‘lovlar ham ozroq bo‘lishi mumkin, lekin ish jarayoni davom etadi. Yuqoridagi jarayon (yangi topshiriq berish, uni bajarish, to‘lovlarni taqsimlash va bajaruvchi xodimning ketishi) Zarif yolg‘iz qolguncha takrorlanadi. Albatta, shu vaqtgacha Mirko katta boylik to‘plagan bo‘ladi, lekin u har bir xodim qancha pul ishlaganini ham bilishni xohlaydi.

Birinchi qatorda ijobiy butun son $N (2 \le N \le 2\times10^5)$ — korporatsiya xodimlari soni (Mirko ham qo‘shilgan).
Keyingi qatorda $a_2, a_3, \dots, a_N$​ ijobiy butun sonlari berilgan, har biri uchun $1 \le a_i < i$,

bu yerda $a_i$ — $i$-chi xodimning rahbari.

Bitta qatorda $N$ ta sonni chop eting: $i-$son korporatsiyadagi $i-$xodim to‘plagan tanga miqdorini ifodalaydi.