Vəzifəyə yüksəltmənin hesablanması#10553
İnəklər yenidən startap şirkəti yaratmağa cəhd etdilər, deyəsən, inəklərin dəhşətli menecerlər olduğunu göstərən keçmiş təcrübəni unudublar!
1, \ldots, n nömrələri ilə rahat şəkildə nömrələnmiş inəklər şirkəti ağac şəklində təşkil edirlər, burada nömrəli inək prezidentdir (ağacın kökü). Prezident istisna olmaqla, hər bir inəyin yeganə meneceri (ağacdakı «valideyni») var. Hər bir inəyinin özünəməxsus peşəkarlıq reytinqi var ki, bu da onun öz işini nə dərəcədə yaxşı yerinə yetirdiyini xarakterizə edir. Əgər inəyi inəyinin əcdadıdırsa (məsələn, meneceri, menecerinin meneceri və ya daha yüksək səviyyədə), onda biz inəyini inəyinin tabeliyində olan inək adlandırırıq.
Təəssüf ki, inəklər aşkar etdilər ki, menecerlərin peşəkarlıq reytinqi çox vaxt onların tabeliyində olan bəzi inəklərin reytinqindən aşağı olur. Belə hallarda menecer öz tabeliyindəki bəzi inəkləri vəzifəcə yüksəltməyi düşünməlidir. Sizin vəzifəniz — inəklərə belə vəziyyətin nə vaxt yarandığını müəyyən etməkdə kömək etməkdir. Hər bir inəyi üçün p(j) > p(i) şərtini ödəyən onun tabeliyindəki inəklərinin sayını hesablayın.
Birinci sətirdə n~(1 \le n \le 10^5) ədədi verilir. Növbəti sətirdə inəklərin p(1), \ldots, p(n) peşəkarlıq reytinqləri verilir. Bütün peşəkarlıq reytinqləri fərqlidir və -dən 10^9-a qədər olan diapazonda tam ədədlərdir.
Növbəti n - 1 sətirdə 2, \ldots, n inəklərinin hər birinin meneceri (valideyni) təsvir olunur. Xatırladaq ki, inəyinin meneceri yoxdur, çünki o, prezidentdir.
sətir çap edin. -ci sətirdə inəyinin tabeliyində olan, peşəkarlıq reytinqi inəyinin reytinqindən yüksək olan inəklərin sayını çap edin.
Nümunə 1