This is the hard version of the problem. In this version, you need to find the answer for every prefix of the monster array.
In a computer game, you are fighting against $$$n$$$ monsters. Monster number $$$i$$$ has $$$a_i$$$ health points, all $$$a_i$$$ are integers. A monster is alive while it has at least $$$1$$$ health point.
You can cast spells of two types:
Dealing $$$1$$$ damage to a monster reduces its health by $$$1$$$.
Spells of type 1 can be cast any number of times, while a spell of type 2 can be cast at most once during the game.
For every $$$k = 1, 2, \ldots, n$$$, answer the following question. Suppose that only the first $$$k$$$ monsters, with numbers $$$1, 2, \ldots, k$$$, are present in the game. What is the smallest number of times you need to cast spells of type 1 to kill all $$$k$$$ monsters?
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
Each test case consists of two lines. The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of monsters.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — monsters' health points.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print $$$n$$$ integers. The $$$k$$$-th of these integers must be equal to the smallest number of times you need to cast spells of type 1 to kill all $$$k$$$ monsters, if only monsters with numbers $$$1, 2, \ldots, k$$$ are present in the game.
233 1 264 1 5 4 1 1
2 1 0 3 2 4 4 4 4
In the first test case, for $$$k = n$$$, the initial health points of the monsters are $$$[3, 1, 2]$$$. It is enough to cast a spell of type 2:
Since it is possible to use no spells of type 1 at all, the answer is $$$0$$$.
In the second test case, for $$$k = n$$$, the initial health points of the monsters are $$$[4, 1, 5, 4, 1, 1]$$$. Here is one of the optimal action sequences:
Spells of type 1 are cast $$$4$$$ times in total. It can be shown that this is the smallest possible number.
Name |
---|