write a go solution for Description:
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<=t<=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<=n<=2*10^5) — the number of monsters.

The second line contains n integers a_1,a_2,ldots,a_n (1<=a_i<=n) — monsters' health points.

It is guaranteed that the sum of n over all test cases does not exceed 2*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.

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.. Output only the code with no comments, explanation, or additional text.