رییس و کارخانه شکلات‌سازی


  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

بعد از انقلاب صنعتی، مربّاها در کارخانه‌های ویژه‌ای که توسط انسان‌ها اداره می‌شود، تولید می‌شوند. در این کارخانه‌ها مراتب اداری از هر چیز دیگری مهم‌تر است.

مراتب اداری در این کارخانه‌ها به این صورت است که آقای شماره‌ی ۱، رییس کارخانه است و همه‌ی کارهای کارخانه زیر نظر او انجام می‌گیرد. پس از رییس کارخانه، کارگران رتبه‌ی اول قرار دارند که همگی تحت فرمان مستقیم رییس کارخانه هستند. همچنین به ازای هر i>1i > 1، هر کارگر رتبه‌ی iiام تحت فرمان مستقیم دقیقا یکی از کارگرهای رتبه‌ی i1i-1 هستند. بعلاوه، اگر انسان xx تحت فرمان انسان yy باشد و انسان yy تحت فرمان انسان zz باشد، انسان xx تحت فرمان انسان zz هم هست و هیچ‌کس دیگری در هیچ‌حالتی (به جز دو حالت تحت فرمان مستقیم و با واسطه که گفته شدند) تحت فرمان کس دیگری نیست.

این سلسله مراتب سخت اداری، برای جلوگیری از فساد به وجود آمده؛ بدین صورت که اگر یک روز ii نفر از افراد تحت‌فرمان مستقیم انسان xx فساد کنند، انسان xx علاوه بر پرداخت جریمه‌ی فساد آن‌ها، باید به تعداد کسانی که به هر ترتیبی تحت فرمان او بودند و ملزم به پرداخت جریمه شده‌اند هم شیشه بپردازد (شیشه واحد پولی مربّاهاست که از قضا بسیار ارزشمند هم هست). همچنین او یک شیشه‌ هم برای تنبیه خودش باید بپردازد. به مجموع هزینه‌ای که انسان xx ملزم به پرداخت آن می‌شود، جریمه‌ی انسان xx می‌گوییم.

در یکی از روزهای گرم و آفتابی تابستان، تمام کسانی که کسی تحت فرمان آن‌ها نبود، فساد کردند و ملزم به پرداخت جریمه‌ی 11شیشه‌ای شدند. امروز جریمه‌ای که رییس باید بپردازد به دستش رسیده. او از مقدار هزینه‌ای که باید بپردازد ناراضی است، به همین دلیل، از شما خواسته هزینه‌ای که او باید بپردازد را تایید کنید.

ورودی🔗

در خط اول ورودی nn تعداد افراد کارخانه می‌آید. در خط دوم ورودی n1n - 1 عدد می‌آید که عدد ii ام، pip_i است که نشان می‌دهد که انسان i+1i+1 تحت فرمان مستقیم انسان pip_i می‌باشد. 1n100 0001 \leq n \leq 100\ 000 1pin1 \leq p_i \leq n تضمین می‌شود که همه‌ی انسان‌ها تحت فرمان رییس کارخانه هستند.

خروجی🔗

در تنها خط خروجی تعداد هزینه‌ای که رییس باید بابت جریمه بپردازد را خروجی دهید.

مثال🔗

ورودی نمونه ۱🔗

5
1 2 1 3
Plain text

خروجی نمونه ۱🔗

12
Plain text

مقدار هزینه‌ای که هر شخص باید بکند به همراه سلسه مراتب کارخانه، به شکل زیر می‌باشد.