This is the hard version of the problem. The difference between the versions is that in this version, (1\le n\le 10^6) and you need to output the answer for each prefix. You can hack only if you solved all versions of this problem. Leo works as a programmer in the city center, and his lover teaches at a high school in the suburbs. Every weekend, Leo would ride his bike to the suburbs to spend a nice weekend with his lover. There are (n) cyclists riding in front of Leo on this road right now. They are numbered (1), (2), (\ldots), (n) from front to back. Initially, Leo is behind the (n)-th cyclist. The (i)-th cyclist has an agility value (a_i). Leo wants to get ahead of the (1)-st cyclist. Leo can take the following actions as many times as he wants: Assuming that the first person in front of Leo is cyclist (i), he can go in front of cyclist (i) for a cost of (a_i). This puts him behind cyclist (i - 1). Using his super powers, swap (a_i) and (a_j) ((1\le i < j\le n)) for a cost of ((j - i)). Leo wants to know the minimum cost to get in front of the (1)-st cyclist. In addition, he wants to know the answer for each (1\le i \le n), (a_1, a_2, \ldots, a_i) as the original array. The problems of different (i) are independent. To be more specific, in the (i)-th problem, Leo starts behind the (i)-th cyclist instead of the (n)-th cyclist, and cyclists numbered (i + 1, i + 2, \ldots, n) are not present. 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. The first line of each test case contains a positive integer (n) ((1 \leq n \leq 10^6)), representing the number of the cyclists. The second line of each test case contains (n) integers (a_1, \ldots, a_n) ((1 \leq a_i \leq 10^9)). It is guaranteed that the sum of (n) over all t