+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- شورای صنفی که از فروش گوسفندان به درآمد بسیاری رسید، تصمیم گرفت با طراحان مسابقه الگوریتم شرکت بزند. در این شرکت n کارمند به صورت هرمی و سلسله مراتبی مشغول کارند. به صورتی که هر کارمند (به جز رئیس شورا) دقیقا یک مدیر اولیه دارد. رئیس شورا مدیر همه‌ی کارمندان است. (از طریق زنجیره‌ای از مدیران اولیه) هر کارمند یک مقدار عددی رتبه دارد. رتبه رئیس شورا برابر ۱ می‌باشد و رتبه هر کارمند دیگر برابر رتبه مدیر اولیه او به علاوه ۱ است. سبحان به عنوان کارمند فعال این شرکت، از جایگزینی هراس دارد و افراد زیادی هم وجود دارند که میتوانند با او جایگزین شوند. او با خودش یک عدد جایگزینی تعریف میکند. برای هر فرد a و b که مدیر او ( نه لزوما اولین مدیر ) است، عدد جایگزینی ($r(a,b)$) a نسبت به b برابر است با تمام زیردستان b که رتبه‌شان از a بیشتر نیست. اما او از آنجا که وسواس زیادی دارد عدد ترس را هم تعریف میکنم که $f_a$ برای فرد a برابر است با مجموع تمام اعداد جایگزینی او نسبت به مدیرهایش. برای مثال داریم: $$f_a = \sum_b r(a,b) $$ که سیگما روی مجموعه تمام مدیران یعنی b اعمال می‌شود. سبحان نه تنها علاقمند به عدد ترس خودش است، بلکه از آنجا که پیش در دانستیم کنجکاو است می‌خواهد عدد ترس همه‌ی کارمندان را حساب کند و از آنجا که در شرکت مشغول است و زمان زیادی ندارد، از شما می‌خواد برایش این اعداد را حساب کنید. # ورودی خط اول شامل تنها یک عدد طبیعی n، یعنی تعداد کارمندان است. $$1 \le n \le 5*10^5$$ خط دوم شامل n عدد $ p_1, p_2,...,p_n $ می‌باشد. $$0 \le p_i \le n$$ $p_i$ برای رئیس شورا ۰ بوده، و برای بقیه $p_i$ها برابر است با شناسه اولین مدیر کارمند با شناسه i. مطمئنیم بین $p_i$ها فقط یک عدد 0 وجود دارد و همچنین رئیس شورا مدیر همه‌ی کارکنان (نه لزوما اولین مدیر) # خروجی خروجی برنامه‌ی شما باید شامل یک خط باشد، که نشان دهنده عدد ترس هر کارمند به ترتیب شناسه او می‌باشد: $$z_1, z_2, ..., z_n $$ # مثال ## ورودی نمونه ۱ ``` 4 0 1 2 1 ``` ## خروجی نمونه ۱ ``` 0 2 4 2 ``` - رئیس شورا مدیری ندارد. پس $f_1 = 0$ - $r(2,1) = 2$ (کارمندان ۲ و ۴ مورد قبول شرط‌اند و کارمند ۳ رتبه بزرگ تری دارد.). پس $f_2= r(2,1) = 2$ - مانند $f_2$ میدانیم: $f_4 = r(4,1) $ - $r(3,2) = 1$ (کارمند ۳ زیردست کارمند ۲ است و رتبه قابل قبول را دارد.). $r(3,1) = 3$ (کارمندان ۲، ۳ و ۴ در شرط صدق می‌کنند.). بنابراین $f_3 = r(3,2) + r(3,1) = 4$ ## ورودی نمونه ۲ ``` 5 0 1 1 1 3 ``` ## خروجی نمونه ۲ ``` 0 3 3 3 5 ```