능력주의 회사 timer 2s memory 512MB

능력을 최우선으로 생각하는 스타트업 회사 매리토크라시는 1…N으로 번호가 매겨진 N명의 직원들이 있다. 그 중 1번은 대표다.

대표를 제외한 각 직원들은 한 명의 직속 상사가 있고, 각 직원 i는 자신의 업무를 얼마나 잘 수행하는지를 나타내는 고유한 숙련도 등급 p(i)를 가지고 있다. 직원 i가 직원 j의 직속 상사의 직속 상사라면 j는 i의 부하 직원이다.

불행하게도 직원들은 직속 상사가 부하 직원 몇 명보다 능력이 떨어지는 경우가 많다는 사실을 알게 되었다. 이 경우 직속 상사는 부하 직원 중 일부를 승진시키는 것을 고려해야 한다.

당신의 임무는 직원들이 언제 이런 일이 일어나는지 알아내도록 돕는 것이다. 회사의 각 직원 i에 대해 p(j)>p(i)인 부하 직원 j의 수를 세는 프로그램을 작성하자.