该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

$Alice$ 正在为她的派对准备蛋糕。然而她时间紧迫，在蛋糕上有一块长度为 $n$ 的区域糖霜分布不均。为了快速解决这个问题， $Alice$ 会将刀放在某个整数高度处，然后从左到右刮平糖霜，使其变得平整。

正式来说，设 $a_i$ 为第 $i$ 个位置的糖霜高度。假设 $Alice$ 将刀放在某个整数高度 $h$ 处。若第 $i$ 个位置的糖霜高度大于 $h$，多余的糖霜将被推至第 $i+1$ 个位置。位于第 $n$ 个位置的糖霜则会完全被推离蛋糕。

$Alice$和她的朋友们非常喜欢蛋糕上的糖霜。由于 $Alice$ 可能决定只切下蛋糕的前缀部分而非整个蛋糕，请帮助她找出对于 $i = 1, 2, \ldots, n$，在保持前 $i$ 个位置糖霜平整的前提下，糖霜能达到的最大高度。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 。

每个测试用例输入两行数据

第一行包含一个整数 $n$, 表示蛋糕的长度

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$, 分别表示每个位置糖霜的高度

输出格式

对于每个测试用例，输出 $n$ 个整数，其中第 $i$ 个整数表示在保持前 $i$ 个位置糖霜水平的情况下，糖霜所能达到的最大高度。

5
3
4 2 3
5
2 3 4 3 2
5
3 3 3 1 1
3
913764826 346182673 764382516
8
6 7 6 7 6 7 6 7

4 3 3 
2 2 2 2 2 
3 3 3 2 2 
913764826 629973749 629973749 
6 6 6 6 6 6 6 6 

样例 1 解释说明

第一个测试用例的解释如下：

当 $i = 1$ 时， $Alice$ 对由数组 $[4]$ 表示的蛋糕感兴趣。由于蛋糕已经是平整的，糖霜能达到的最大高度为 $4$。

当 $i = 2$ 时， $Alice$ 对由数组 $[4, 2]$ 表示的蛋糕感兴趣。如果 $Alice$ 将刀放在高度 $4$ 处，得到的蛋糕糖霜高度为 $[4, 2]$，导致蛋糕不平整。然而，如果 $Alice$ 将刀放在高度 $3$ 处，一个单位的糖霜将从第一个位置推到第二个位置，使得得到的蛋糕糖霜高度为 $[3, 3]$，这是平整的。因此，在保持平整的情况下，糖霜能达到的最大高度为 $3$。

当 $i = 3$ 时，如果 $Alice$ 将刀放在高度 $4$ 处，得到的糖霜高度为 $[4, 2, 3]$。然而，如果 $Alice$ 将刀放在高度 $3$ 处，得到的糖霜高度为 $[3, 3, 3]$。因此，在保持平整的情况下，糖霜能达到的最大高度为 $3$。

数据规模与约定

对于 $100\%$ 的数据

• $1 \le T \le 10^4$。
• $2 \leq n \leq 2\cdot 10^5$ 且 $\sum_{i=1}^Tn \le 2\times 10^5$
• $1 \leq a_i \leq 10^9, 1\le i\le n$