CF2107F2.Cycling (Hard Version)

这是此问题的困难版本，和其他版本的区别是此版本中 $1\le n\le 10^6$，且需要对每个前缀都求解。

Leo 骑车去见他的女朋友。在 Leo 的前面有 $n$ 名骑手，从前往后排在第 $i$ 名的骑手的灵活度为 $a_i$。

Leo 将要加速超过前面的所有骑手，他可以执行以下两种操作：

• 当他在骑手 $i$ 后面，骑手 $i+1$ 前面（或 $i=n$）时，付出 $a_i$ 的代价超过骑手 $i$，之后他将在骑手 $i$ 前面，骑手 $i-1$ 后面（如果 $i>1$）；
• 使用他的超级力量交换 $a_i$ 和 $a_j$，代价为 $\vert i-j\vert$。

请你找出超过所有 $n$ 名骑手的最小代价。

额外地，Leo 想知道对于每个 $i(1\le i\le n)$，当只有骑手 $1,2,\cdots,i$ 存在时，他超过所有 $i$ 名骑手的最小代价。

多组数据，第一行一个整数 $t(1\le t\le 10^4)$，表示数据组数。

对于每组数据，第一行一个整数 $n(1\le n\le 10^6)$。
第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n(1\le a_i\le 10^9)$。

保证单个测试点中 $\sum n\le 10^6$。

对于每组数据，输出一行 $n$ 个整数，第 $i$ 个数表示只存在前 $i$ 个骑手时的答案。

样例解释

第一组数据中，当存在所有 $n$ 名骑手时，一组操作如下所示：

• 交换 $a_2$ 和 $a_3$，之后 $a=(1,4,2)$，代价为 $1$；
• 超过第 $3$ 名骑手，代价为 $2$；
• 交换 $a_1$ 和 $a_2$，$a=(4,1,2)$，代价为 $1$；
• 超过第 $2$ 名骑手，代价为 $1$；
• 交换 $a_1$ 和 $a_2$，$a=(1,4,2)$，代价为 $1$；
• 超过第 $1$ 名骑手，代价为 $1$。

总代价为 $7$。可以证明这是最小的代价。

第二组数据中，当存在所有 $n$ 名骑手时，如果一直执行“超过”操作，花费为 $4$。可以证明这是最小的代价。

By chenxi2009