F. Уменьшение массива
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$, содержащий $$$n$$$ целых чисел.

За одну операцию вы можете выбрать некоторые элементы из этого массива и удалить их. Однако выбранные вами элементы должны соответствовать одному из следующих условий:

  • либо все выбранные элементы равны;
  • либо среди выбранных элементов нет двух равных.

Обратите внимание, что если вы выбираете только $$$1$$$ элемент для удаления, он автоматически соответствует этим условиям.

Например, если $$$a = \{1, 2, 1, 1, 3\}$$$, некоторые из возможных элементов, которые вы можете удалить за одну операцию, это:

  • $$$1$$$-й элемент;
  • $$$1$$$-й и $$$3$$$-й элементы;
  • $$$1$$$-й, $$$3$$$-й и $$$4$$$-й элементы;
  • $$$3$$$-й и $$$4$$$-й элементы;
  • $$$2$$$-й, $$$4$$$-й и $$$5$$$-й элементы;
  • и многие другие.

Однако вы не можете выбрать $$$2$$$-й, $$$3$$$-й и $$$4$$$-й элементы, потому что $$$2$$$-й элемент не равен $$$4$$$-му, но $$$3$$$-й элемент равен $$$4$$$-му.

Для каждого $$$x$$$ от $$$0$$$ до $$$n - 1$$$ вам необходимо вычислить минимальное количество операций, необходимых для уменьшения размера массива до ровно $$$x$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк:

  • первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — размер массива;
  • вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — сам массив.

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$c_0, c_1, \dots, c_{n-1}$$$, где $$$c_i$$$ — минимальное количество операций, необходимых для уменьшения размера массива до ровно $$$i$$$.

Пример
Входные данные
5
11
5 5 5 5 2 2 2 8 6 1 7
6
3 3 3 3 3 3
5
2 1 3 5 4
8
1 1 1 2 3 4 5 6
1
1
Выходные данные
3 3 2 2 2 1 1 1 1 1 1 
1 1 1 1 1 1 
1 1 1 1 1 
2 2 1 1 1 1 1 1 
1
Примечание

В первом наборе входных данных ответ можно получить следующим образом:

  • $$$c_{0} = 3$$$: удалить $$$a_{8}, a_{9}, a_{10}, a_{11}$$$; затем удалить $$$a_{1}, a_{2}, a_{3}, a_{4}$$$; затем удалить $$$a_{5}, a_{6}, a_{7}$$$;
  • $$$c_{1} = 3$$$: удалить $$$a_{8}, a_{9}, a_{10}, a_{11}$$$; затем удалить $$$a_{1}, a_{2}, a_{3}, a_{4}$$$; затем удалить $$$a_{5}, a_{6}$$$;
  • $$$c_{2} = 2$$$: удалить $$$a_{7}, a_{8}, a_{9}, a_{10}, a_{11}$$$; затем удалить $$$a_{1}, a_{2}, a_{3}, a_{4}$$$;
  • $$$c_{3} = 2$$$: удалить $$$a_{7}, a_{8}, a_{9}, a_{10}, a_{11}$$$; затем удалить $$$a_{1}, a_{2}, a_{3}$$$;
  • $$$c_{4} = 2$$$: удалить $$$a_{7}, a_{8}, a_{9}, a_{10}, a_{11}$$$; затем удалить $$$a_{1}, a_{2}$$$;
  • $$$c_{5} = 1$$$: удалить $$$a_{1}, a_{7}, a_{8}, a_{9}, a_{10}, a_{11}$$$;
  • $$$c_{6} = 1$$$: удалить $$$a_{7}, a_{8}, a_{9}, a_{10}, a_{11}$$$;
  • $$$c_{7} = 1$$$: удалить $$$a_{1}, a_{2}, a_{3}, a_{4}$$$;
  • $$$c_{8} = 1$$$: удалить $$$a_{1}, a_{2}, a_{3}$$$;
  • $$$c_{9} = 1$$$: удалить $$$a_{1}, a_{2}$$$;
  • $$$c_{10} = 1$$$: удалить $$$a_{7}$$$;