Олимпиадный тренинг

Задача . D. Слизни


Задача

Темы: Бинарный поиск два указателя жадные алгоритмы Конструктив Структуры данных *1800

В линию расположено \(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, если это невозможно.


Примеры
№Входные данныеВыходные данные
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

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет