B"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 <= 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 cdot 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 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. 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"...