B. Игра в коллекционирование
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ из $$$n$$$ целых положительных чисел и счет. Если ваш счет больше или равен $$$a_i$$$, то вы можете увеличить свой счет на $$$a_i$$$ и удалить $$$a_i$$$ из массива.

Для каждого индекса $$$i$$$ выведите максимальное количество дополнительных элементов массива, которые вы можете удалить, если удалите $$$a_i$$$ и начнёте со счетом, равным $$$a_i$$$. Обратите внимание, что удаление $$$a_i$$$ не должно учитываться в ответе.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 5000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите $$$n$$$ целых чисел, $$$i$$$-е из которых обозначает максимальное количество дополнительных элементов массива, которые можно удалить, если удалить из массива $$$a_i$$$ и начать со счетом $$$a_i$$$.

Пример
Входные данные
4
5
20 5 1 4 2
3
1434 7 1442
1
1
5
999999999 999999999 999999999 1000000000 1000000000
Выходные данные
4 3 0 3 1 
1 0 2 
0 
4 4 4 4 4
Примечание

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

Если мы начинаем с $$$i=4$$$, то наш изначальный счет равен $$$a_4=4$$$ и $$$a=[20,5,1,2]$$$. Мы можем удалить $$$3$$$ дополнительных элемента в следующем порядке:

  1. Поскольку $$$4 \ge 1$$$, мы можем удалить $$$1$$$, и наш счет станет равен $$$5$$$. После этого $$$a=[20,5,2]$$$.
  2. Поскольку $$$5 \ge 5$$$, мы можем удалить $$$5$$$ и наш счет станет $$$10$$$. После этого $$$a=[20,2]$$$.
  3. Поскольку $$$10 \ge 2$$$, мы можем удалить $$$2$$$, и наш счет станет $$$12$$$. После этого $$$a=[20]$$$.

Если мы начнем с $$$i=1$$$, то сможем удалить все оставшиеся элементы массива, поэтому ответ будет $$$4$$$.

Если мы начнем с $$$i=2$$$, то сможем удалить $$$3$$$ дополнительных элемента в следующем порядке: $$$1$$$, $$$4$$$, $$$2$$$.

Если мы начнем с $$$i=3$$$, то не сможем удалить ни одного дополнительного элемента.

Если мы начинаем с $$$i=5$$$, то можем удалить $$$1$$$ дополнительный элемент: $$$1$$$.