每个测试时间限制：5 秒
每个测试内存限制：1024 兆字节

---

题目说明

这是该问题的困难版本。两个版本的区别在于，在此版本中 $1 \le n \le 10^6$，并且你需要为每个前缀输出答案。只有当你解决了该问题的所有版本时，才能进行 Hack。

Leo 在市中心做程序员，他的爱人在郊区的一所高中教书。每个周末，Leo 都会骑自行车去郊区与爱人共度美好周末。

此刻，Leo 前方的道路上共有 $n$ 名骑行者在骑行。他们从前到后编号为 $1, 2, \dots, n$。初始时，Leo 位于第 $n$ 名骑行者的后面。第 $i$ 名骑行者有一个敏捷值 $a_i$。

Leo 想要骑到第 $1$ 名骑行者前面。Leo 可以无限次地执行以下操作：

• 假设 Leo 前方的第一个骑行者是 $i$，他可以花费 $a_i$ 的成本骑到他前面。这会使他位于第 $i-1$ 名骑行者之后（如果 $i=1$，则表示他已经位于第 $1$ 名骑行者前面）。
• 使用他的超能力，花费 $(j-i)$ 的成本交换 $a_i$ 和 $a_j$（$1 \le i < j \le n$）。

Leo 想知道骑到第 $1$ 名骑行者前面的最小成本。

此外，他还想知道对于每个 $1 \le i \le n$，以 $[a_1, a_2, \dots, a_i]$ 作为原始数组时的答案。不同 $i$ 的问题是相互独立的。具体来说，在第 $i$ 个问题中，Leo 从第 $i$ 名骑行者后面开始（而不是第 $n$ 名后面），且编号为 $i+1, i+2, \dots, n$ 的骑行者不存在。

---

输入格式

每个测试包含多个测试用例。
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
接下来每个测试用例的格式如下：

• 第一行包含一个正整数 $n$（$1 \le n \le 10^6$），表示骑行者的数量。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

数据保证所有测试用例的 $n$ 之和不超过 $10^6$。

---

输出格式

对于每个测试用例，输出 $n$ 个整数，分别对应数组 $[a_1, a_2, \dots, a_i]$ 的答案（$i = 1, 2, \dots, n$），按顺序输出。

---

示例

输入

4
3
1 2 4
4
1 1 1 1
2
1 2
4
4 1 3 2

输出

1 3 7
1 2 3 4
1 3
4 3 6 8

---

样例解释

第一个测试用例：
一种可能的移动方式如下（针对 $i=3$ 即完整数组）：

1. Leo 交换 $a_2$（$i=2$）和 $a_3$（$j=3$），数组变为 $[1,4,2]$，花费 $j-i = 3-2 = 1$。
2. Leo 位于第 $3$ 名骑行者后面，移动到第 $2$ 名骑行者后面，花费 $a_3 = 2$。
3. Leo 交换 $a_1$（$i=1$）和 $a_2$（$j=2$），数组变为 $[4,1,2]$，花费 $j-i = 2-1 = 1$。
4. Leo 位于第 $2$ 名骑行者后面，移动到第 $1$ 名骑行者后面，花费 $a_2 = 1$。
5. Leo 交换 $a_1$（$i=1$）和 $a_2$（$j=2$），数组变为 $[1,4,2]$，花费 $j-i = 2-1 = 1$。
6. Leo 移动到第 $1$ 名骑行者前面，花费 $a_1 = 1$。

总成本为 $1+2+1+1+1+1 = 7$。可以证明 $7$ 是最小成本。

对于 $i=1$：只有 $[1]$，Leo 直接在前面，成本 $1$。
对于 $i=2$：$[1,2]$，一种最优策略是不交换，依次超车 $2$ 和 $1$，成本 $2+1=3$。
输出 $1, 3, 7$。

第二个测试用例：
所有 $a_i = 1$，对于前缀 $i$，依次超车成本 $1+1+\dots+1 = i$，无需交换。输出 $1,2,3,4$。