CF1393C Pinkie Pie Eats Patty-cakes

Pinkie Pie 买了一袋有不同馅料的馅饼！但实际上，并不是所有馅饼的馅料都不同。换句话说，这袋子里有一些馅饼的馅料是相同的。 Pinkie Pie 会一个接一个地吃掉这些馅饼。她喜欢找乐子，所以她决定不只是简单地吃掉这些馅饼，而是尽量避免连续吃到相同馅料的馅饼。为此，她希望吃到相同馅料的馅饼之间的最小距离尽可能大。这里，Pinkie Pie 所说的两个馅饼之间的距离，是指它们之间被吃掉的馅饼的数量（严格在它们之间的馅饼数）。 Pinkie Pie 可以以任意顺序吃掉这些馅饼。她迫不及待地想把所有馅饼都吃完，所以她请你帮忙计算，在所有可能的吃法中，吃到相同馅料的馅饼之间的最大最小距离是多少！ Pinkie Pie 还打算买更多袋馅饼，所以她请你帮她解决多个袋子的这个问题！

第一行包含一个整数 $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$。

对于每个袋子，输出一行一个整数，表示在所有可能的吃法中，吃到相同馅料的馅饼之间的最大最小距离。

对于第一个袋子，Pinkie Pie 可以按以下顺序吃馅饼（按馅料编号）：$1$，$6$，$4$，$7$，$1$，$6$，$4$（这样，最小距离为 $3$）。 对于第二个袋子，Pinkie Pie 可以按以下顺序吃馅饼（按馅料编号）：$1$，$4$，$6$，$7$，$4$，$1$，$6$，$4$（这样，最小距离为 $2$）。 由 ChatGPT 4.1 翻译