Это сложная версия задачи. В этой версии задачи ответ нужно вычислить для каждого префикса массива монстров.
В компьютерной игре вы сражаетесь против \(n\) монстров. Монстр с номером \(i\) имеет \(a_i\) единиц здоровья, где \(a_i\) — целое число. Монстр жив, пока имеет хотя бы \(1\) единицу здоровья.
Вы можете использовать заклинания двух типов:
- Нанести \(1\) единицу урона любому живому монстру на ваш выбор.
- Нанести \(1\) единицу урона всем живым монстрам. Если хотя бы один монстр умирает (оказывается с \(0\) единицами здоровья) в результате этого действия — повторить его (и продолжать повторять, пока хотя бы один монстр умирает после каждого применения).
При нанесении \(1\) единицы урона здоровье монстра уменьшается на \(1\).
Заклинания типа 1 могут быть использованы сколько угодно раз, а заклинание типа 2 — не более одного раза за игру.
Для каждого \(k = 1, 2, \ldots, n\) ответьте на следующий вопрос. Пусть в игре присутствуют только первые \(k\) монстров, с номерами \(1, 2, \ldots, k\). Какое наименьшее число раз вам нужно применить заклинания типа 1, чтобы убить всех \(k\) монстров?
Выходные данные
Для каждого набора входных данных выведите \(n\) целых чисел. \(k\)-е из этих чисел должно быть равно наименьшему числу раз, которое нужно применить заклинания типа 1, чтобы убить всех \(k\) монстров, если в игре присутствуют только монстры с номерами \(1, 2, \ldots, k\).
Примечание
В первом наборе входных данных при \(k = n\) начальные значения здоровья у монстров равны \([3, 1, 2]\). Достаточно применить заклинание типа 2:
- Здоровья монстров становятся равны \([2, 0, 1]\). Так как монстр номер \(2\) умер, заклинание повторяется.
- Здоровья монстров становятся равны \([1, 0, 0]\). Так как монстр номер \(3\) умер, заклинание повторяется.
- Здоровья монстров становятся равны \([0, 0, 0]\). Так как монстр номер \(1\) умер, заклинание повторяется.
- Здоровья монстров становятся равны \([0, 0, 0]\).
Так как можно обойтись вообще без заклинаний типа 1, ответ равен \(0\).
Во втором наборе входных данных при \(k = n\) начальные значения здоровья у монстров равны \([4, 1, 5, 4, 1, 1]\). Одной из оптимальных является следующая последовательность действий:
- Используя заклинание типа 1, нанести \(1\) единицу урона монстру номер \(1\). Здоровья монстров становятся равны \([3, 1, 5, 4, 1, 1]\).
- Используя заклинание типа 1, нанести \(1\) единицу урона монстру номер \(4\). Здоровья монстров становятся равны \([3, 1, 5, 3, 1, 1]\).
- Используя заклинание типа 1, снова нанести \(1\) единицу урона монстру номер \(4\). Здоровья монстров становятся равны \([3, 1, 5, 2, 1, 1]\).
- Использовать заклинание типа 2:
- Здоровья монстров становятся равны \([2, 0, 4, 1, 0, 0]\). Так как монстры номер \(2\), \(5\) и \(6\) умерли, заклинание повторяется.
- Здоровья монстров становятся равны \([1, 0, 3, 0, 0, 0]\). Так как монстр номер \(4\) умер, заклинание повторяется.
- Здоровья монстров становятся равны \([0, 0, 2, 0, 0, 0]\). Так как монстр номер \(1\) умер, заклинание повторяется.
- Здоровья монстров становятся равны \([0, 0, 1, 0, 0, 0]\).
- Используя заклинание типа 1, нанести \(1\) единицу урона монстру номер \(3\). Здоровья монстров становятся равны \([0, 0, 0, 0, 0, 0]\).
Всего заклинания типа 1 были применены \(4\) раза. Можно показать, что это наименьшее возможное число.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
3
3 1 2
6
4 1 5 4 1 1
|
2 1 0
3 2 4 4 4 4
|