← 返回题目列表

Codeforces · 1393/C

C. 萍琪派吃馅饼

中文机器翻译题面 查看原题

萍琪派买了一袋不同馅料的馅饼!但似乎并不是所有的馅饼的馅料都各有不同。换句话说,袋子里装的是一些同样馅料的肉饼。

萍琪派一张一张地吃着馅饼。她喜欢玩,所以她决定不再简单地吃肉饼,而是尽量不要经常吃同一种馅料的肉饼。为了实现这一目标,她希望具有相同馅料的食物之间的最小距离尽可能最大。在这里,萍琪派将两个馅饼之间的距离严格地称为它们之间吃掉的馅饼的数量。

萍琪派可以按任意顺序吃馅饼。她迫不及待地想把所有的肉饼吃完,所以她​​要求你帮她计算在所有可能的吃顺序中,吃完的相同馅料的肉饼之间的最大最小距离!

萍琪派要买更多袋的馅饼,所以她要求你解决几袋的问题!

输入

第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 100$$$):您需要解决问题的袋子数量。

每个袋子描述的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$):其中的馅饼数量。袋子描述第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$):饼馅的信息:相同的馅料定义为相同的整数,不同的馅料定义为不同的整数。保证每袋至少含有两个相同馅料的肉饼。

保证所有行李的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个袋子,在单独的行中打印一个整数:在该袋子的所有可能的食用顺序中,所吃的具有相同填充物的馅饼之间的最大最小距离。

示例

输入 #1

4
7
1 7 1 6 4 4 6
8
1 1 4 6 4 6 4 7
3
3 3 3
6
2 5 2 3 1 4

输出 #1

3
2
0
4

注意

对于第一袋,萍琪派可以按以下顺序吃馅饼(按馅料):$$$1$$$、$$$6$$$、$$$4$$$、$$$7$$$、$$$1$$$、$$$6$$$、$$$4$$$(这样,最小距离等于$$$3$$$)。

对于第二袋,萍琪派可以按以下顺序吃馅饼(按馅料):$$$1$$$、$$$4$$$、$$$6$$$、$$$7$$$、$$$4$$$、$$$1$$$、$$$6$$$、$$$4$$$(这样,最小距离等于$$$2$$$)。