마피아

$n$명의 조직원이 팽팽하게 대치하고 있다. 각 조직원은 권총을 뽑아 들고 $n$명 중 정확히 한 명(자기 자신일 수도 있다)을 계속 겨누고 있다. 총격이 시작되면 다음 규칙에 따라 진행된다.

• 조직원들은 어떤 순서로 한 명씩 발사하며, 어느 순간에도 발사하는 사람은 최대 한 명이다.
• 발사한 사람은 절대 빗맞히지 않는다. 표적은 즉시 사망하며 더 이상 발사할 수 없다.
• 모든 조직원은 자기 차례가 오기 전에 사살되지 않는 한 정확히 한 번 발사한다.
• 조직원은 겨누던 표적을 바꾸지 않는다. 발사하는 순간 그 표적이 이미 죽어 있다면 총알은 시신에 맞을 뿐 새로운 사망자를 내지 않는다.

조직원들이 발사하는 순서는 정해져 있지 않으며, 순서에 따라 사망자 수가 달라질 수 있다. 누가 누구를 겨누는지만 주어졌을 때, 가능한 모든 발사 순서에 대해 사망자 수의 최솟값과 최댓값을 구하여라.

첫째 줄에 조직원의 수 $n$ ($1 \le n \le 1{,}000{,}000$)이 주어진다. 조직원은 $1$번부터 $n$번까지 번호가 매겨져 있다.

둘째 줄에 $n$개의 정수 $s_1, s_2, \ldots, s_n$ ($1 \le s_i \le n$)이 공백 하나로 구분되어 주어진다. $s_i$는 $i$번 조직원이 겨누는 표적의 번호이다. $s_i = i$인 경우도 가능하며, 이는 $i$번 조직원이 자기 자신을 겨눈다는 뜻이다.

첫째 줄에 사망자 수의 최솟값과 최댓값을 공백 하나로 구분하여 두 정수로 출력한다.