Bajtazar는 한때 상당한 우표 수집품을 모았습니다. 하지만 젊었을 때만큼 관심이 없어진 그는 자신의 수집품을 어린 우표 수집가들에게 나누어 주기로 결심했습니다. 그는 가능한 한 공정하게 나누어 주고 싶어 하며, 이를 위해 당신의 도움이 필요합니다.

Bajtazar의 수집품은 $n$개의 우표로 구성되어 있으며, $i$번째 우표는 도시 $a_i$에서 왔습니다. 편의상 도시들은 정수로 표시합니다. Bajtazar는 우표를 나누어 주겠다는 광고를 신문에 낼 예정입니다. 만약 $k$명의 지원자가 나타나면, 그는 각 지원자에게 어떤 조건에 따라 우표의 부분집합을 선물할 것입니다. 그 조건은 모든 지원자가 동일한 다중집합(multiset)의 우표를 받아야 한다는 것입니다. 즉, 임의의 두 지원자와 임의의 도시에 대해, 두 지원자는 해당 도시에서 온 우표를 동일한 개수만큼 받아야 합니다. 이는 특정 경우에 Bajtazar가 아무런 우표도 나누어 주지 않을 수도 있음을 의미합니다.

Bajtazar는 정확히 몇 명의 지원자가 나타날지 모릅니다. 따라서 $1$부터 $n$까지의 각 $k$에 대해, $k$명의 지원자가 나타났을 때 Bajtazar가 나누어 줄 수 있는 최대 우표 개수를 구해야 합니다.

입력

첫 번째 줄에는 Bajtazar의 수집품에 있는 우표의 개수를 나타내는 정수 $n$ ($1 \le n \le 300\,000$)이 주어집니다.

두 번째 줄에는 Bajtazar의 우표들이 각각 어느 도시에서 왔는지를 나타내는 $n$개의 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)이 주어집니다.

출력

한 줄에 $n$개의 정수를 공백으로 구분하여 출력하십시오. $k$번째 숫자는 $k$명의 지원자가 나타났을 때 Bajtazar가 나누어 줄 수 있는 최대 우표 개수여야 합니다.

예제

입력 1

9
1 1 777 42 777 1 42 1 777

출력 1

9 8 6 4 0 0 0 0 0

참고

예제 설명: 만약 Bajtazar에게 한 명의 지원자가 나타나면, Bajtazar는 모든 우표를 그에게 줄 수 있습니다.

두 명의 지원자가 나타나면, Bajtazar는 각 지원자에게 도시 1에서 온 우표 2개, 도시 42에서 온 우표 1개, 도시 777에서 온 우표 1개씩을 줄 수 있으며, 총 8개의 우표를 나누어 줄 수 있습니다.

네 명의 지원자가 나타나면, Bajtazar는 각 지원자에게 도시 1에서 온 우표 1개씩을 줄 수 있습니다.

네 명보다 많은 지원자가 나타나면, Bajtazar는 어떤 우표도 나누어 줄 수 없습니다.