D. Слизни
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В линию расположено $$$n$$$ слизней. Слизни нумеруются от $$$1$$$ до $$$n$$$ слева направо. Размер $$$i$$$-го слизня равен $$$a_i$$$.

Каждую секунду происходит следующее: ровно один слизень съедает одного из своих соседей и увеличивает свой размер на значение размера соседа. Слизень может съесть своего соседа, только если он строго больше этого соседа. Если нет такого слизня, который больше хотя бы одного из его соседей — процесс завершается.

Например, предположим, что $$$n = 5$$$, $$$a = [2, 2, 3, 1, 4]$$$. Процесс может пройти следующим образом:

  • сначала $$$3$$$-й слизень съедает $$$2$$$-го. Размер $$$3$$$-го слизня становится равным $$$5$$$, $$$2$$$-й слизень съеден.
  • затем $$$3$$$-й слизень съедает $$$1$$$-го (они соседи, так как $$$2$$$-й уже съеден). Размер $$$3$$$-го слизня становится равным $$$7$$$, $$$1$$$-й слизень съеден.
  • затем $$$5$$$-й слизень съедает $$$4$$$-го. Размер $$$5$$$-го слизня становится равным $$$5$$$, $$$4$$$-й слизень съеден.
  • затем $$$3$$$-й слизень съедает $$$5$$$-го (они соседи, так как $$$4$$$-й уже съеден). Размер $$$3$$$-го слизня становится равным $$$12$$$, $$$5$$$-й слизень съеден.

Для каждого слизня вычислите минимальное количество секунд, за которое он может оказаться съеден каким-то другим слизнем (среди всех возможных вариантов, как может происходить процесс), или сообщите, что это невозможно.

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

Первая строка содержит одно целое число $$$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 10^9$$$).

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.

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

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

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