Пинки Пай купила пакет пирожных с разными начинками! Но оказалось, что не все пирожные различаются начинкой между собой, то есть в пакете есть какие-то пирожные с одинаковой начинкой.
Пинки Пай ест пирожные по одному подряд. Она любит веселиться, поэтому решила не просто поедать пирожные, а стараться не есть пирожные с одной начинкой слишком часто. Для этого она хочет, чтобы минимальное расстояние между съеденными пирожными с одинаковой начинкой было как можно больше. При этом расстоянием между двумя пирожными Пинки Пай решила назвать количество съеденных пирожных между ними.
Пинки Пай может поедать пирожные в любом порядке. Ей не терпится скорее съесть все пирожные, поэтому она просит вас помочь посчитать наибольшее минимальное расстояние между съеденными пирожными с одинаковой начинкой среди всех возможных порядков поедания!
Пинки Пай собирается покупать еще пакеты с пирожными, поэтому просит вас решить задачу для нескольких пакетов!
Выходные данные
Для каждого пакета в отдельной выведите одно целое число — наибольшее минимальное расстояние между съеденными пирожными с одинаковой начинкой среди всех возможных порядков поедания пирожных из этого пакета.
Примечание
Для первого пакета Пинки Пай может есть пирожные в следующем порядке (по начинкам): \(1\), \(6\), \(4\), \(7\), \(1\), \(6\), \(4\) (таким образом, минимальное расстояние будет равно \(3\)).
Для второго пакета Пинки Пай может есть пирожные в следующем порядке (по начинкам): \(1\), \(4\), \(6\), \(7\), \(4\), \(1\), \(6\), \(4\) (таким образом, минимальное расстояние будет равно \(2\)).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
3
2
0
4
|