Monsters (hard version)
Contest: VK Cup 2022 - Финальный раунд (Engine)
Difficulty rating: 2200
Tags: data structures, greedy

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:

1. Deal $$$1$$$ damage to any single alive monster of your choice.
2. Deal $$$1$$$ damage to all alive monsters. If at least one monster dies (ends up with $$$0$$$ health points) as a result of this action, then repeat it (and keep repeating while at least one monster dies every time).

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?

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
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:

- Monsters' health points change to $$$[2, 0, 1]$$$. Since monster number $$$2$$$ dies, the spell is repeated.
- Monsters' health points change to $$$[1, 0, 0]$$$. Since monster number $$$3$$$ dies, the spell is repeated.
- Monsters' health points change to $$$[0, 0, 0]$$$. Since monster number $$$1$$$ dies, the spell is repeated.
- Monsters' health points change to $$$[0, 0, 0]$$$.

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:

- Using a spell of type 1, deal $$$1$$$ damage to monster number $$$1$$$. Monsters' health points change to $$$[3, 1, 5, 4, 1, 1]$$$.
- Using a spell of type 1, deal $$$1$$$ damage to monster number $$$4$$$. Monsters' health points change to $$$[3, 1, 5, 3, 1, 1]$$$.
- Using a spell of type 1, deal $$$1$$$ damage to monster number $$$4$$$ again. Monsters' health points change to $$$[3, 1, 5, 2, 1, 1]$$$.
- Use a spell of type 2:  Monsters' health points change to $$$[2, 0, 4, 1, 0, 0]$$$. Since monsters number $$$2$$$, $$$5$$$, and $$$6$$$ die, the spell is repeated.  Monsters' health points change to $$$[1, 0, 3, 0, 0, 0]$$$. Since monster number $$$4$$$ dies, the spell is repeated.  Monsters' health points change to $$$[0, 0, 2, 0, 0, 0]$$$. Since monster number $$$1$$$ dies, the spell is repeated.  Monsters' health points change to $$$[0, 0, 1, 0, 0, 0]$$$.
- Using a spell of type 1, deal $$$1$$$ damage to monster number $$$3$$$. Monsters' health points change to $$$[0, 0, 0, 0, 0, 0]$$$.

Spells of type 1 are cast $$$4$$$ times in total. It can be shown that this is the smallest possible number.

Example input:
2
3
3 1 2
6
4 1 5 4 1 1

Example output:
2 1 0
3 2 4 4 4 4

Editorial:
Continuing on the solution to the easy version: now we have a set of integers $$$A$$$, we need to add elements into $$$A$$$ one by one and maintain the answer to the problem.
Recall that for every $$$i$$$, either $$$b_i = b_{i-1}$$$ or $$$b_i = b_{i-1} + 1$$$. Note that $$$b_i = b_{i-1}$$$ can only happen when $$$b_i = a_i$$$. Let's call such an element useless. If we remove a useless element, the answer does not change.
If there are no useless elements, we have $$$b_1 = 1$$$ and $$$b_i = b_{i-1} + 1$$$ for $$$i > 1$$$: that is, $$$b_i = i$$$. Thus, the answer to the problem can be easily calculated as $$$\sum \limits_{i=1}^m (a_i - b_i) = \sum \limits_{i=1}^m a_i - \frac{m(m+1)}{2}$$$, where $$$m$$$ is the current size of the set.
We can formulate the condition "there are no useless elements" as follows. For any $$$x$$$, let $$$k_x$$$ be the number of elements in $$$A$$$ not exceeding $$$x$$$. Then, $$$k_x \le x$$$.
On the other hand, suppose that for some $$$x$$$, we have $$$k_x > x$$$. Let's find the smallest such $$$x$$$. Then, we can see that $$$A$$$ contains a useless element equal to $$$x$$$, and we can safely remove it.
We can check this condition after adding each new element to $$$A$$$ using a segment tree. In every cell $$$x$$$ of the array maintained by the segment tree, we will store the difference $$$x - k_x$$$. Initially, cell $$$x$$$ contains value $$$x$$$. When a new element $$$v$$$ appears, we should subtract $$$1$$$ from all cells in range $$$[v; n]$$$. Then, if a cell with a negative value appears (that is, $$$x - k_x < 0$$$, which is equivalent to $$$k_x > x$$$), we should find the leftmost such cell $$$x$$$ and remove an element equal to $$$x$$$. In particular, we should add $$$1$$$ to all cells in range $$$[x; n]$$$.
Thus, we can use a segment tree with "range add" and "global min". At most one useless element can appear every time we enlarge $$$A$$$, and if that happens, we can identify and remove it in $$$O(\log n)$$$, resulting in an $$$O(n \log n)$$$ time complexity.