题目背景

PA 2024 2C

题目描述

题目译自 PA 2024 Runda 2 Znaczki pocztowe

Byteasar 曾经收集了大量邮票。然而，他对邮票的兴趣已不如年轻时，因此他决定将自己的邮集赠送给更年轻的集邮爱好者。不过，他希望尽可能公平地完成这项工作，为此他需要你的帮助。

Bytesar 的邮集由 $n$ 张邮票组成，其中第 $i$ 张来自城市 $a_i$。为简单起见，我们用整数表示这些城市。Byteasar 打算在报纸上刊登一则公告，宣布他计划赠送自己的收藏的邮票。如果有 $k$ 个人愿意接收，他将在如下条件下向每个人赠送一个邮票的子集：每个人都必须收到相同的邮票多重集。这就意味着，对于每两个申请人和每个城市，两个申请人都必须从该城市获得相同数量的邮票。特别地，这可能意味着 Byteasar 将不发放任何邮票。

Byteasar 不知道会有多少人前来接收。因此，对于 $1$ 到 $n$ 范围内的每个数 $k$，你需要找出如果有 $k$ 个人愿意接收，Byteasar 最多可以分发多少张邮票。

输入格式

第一行一个整数 $n\ (1\le n\le 300\,000)$，表示 Byteasar 收藏的邮票数量。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (1\le a_i\le 10^9)$，表示 Byteasar 的邮票所来自城市的编号。

输出格式

输出一行 $n$ 个整数，第 $k$ 个整数表示如果有 $k$ 个人愿意接收 Byteasar 的邮票，Byteasar 最多能分发多少张邮票。

9
1 1 777 42 777 1 42 1 777

9 8 6 4 0 0 0 0 0

提示

如果有一个人愿意接收，Byteasar 可以把所有邮票都给他。

如果有两个人，Byteasar 可以给他们每人两张 $1$ 号城镇的邮票、一张 $42$ 号城镇的邮票和一张 $777$ 号城镇的邮票，即总共 $8$ 张邮票。

如果有四个人，Byteasar 可以给他们每人一张 $1$ 号城市的邮票。

如果愿意接收的人数超过四人，Byteasar 将无法送出任何邮票。