题目描述

Alice 正在为派对准备蛋糕，但蛋糕表面的糖霜高度并不平整。她会把刀放在某个整数高度 $h$，然后从左往右刮过糖霜，使糖霜变平。

形式化地，设第 $i$ 个位置的糖霜高度为 $a_i$。如果第 $i$ 个位置的高度大于 $h$，多余的糖霜会被推到第 $i+1$ 个位置；第 $n$ 个位置多余的糖霜会被直接推掉。

Alice 可能只分给朋友们蛋糕的一个前缀。对于每个 $i=1,2,\ldots,n$，请你求出只考虑前 $i$ 个位置时，能让这 $i$ 个位置最终高度相等的最大整数高度。

输入格式

第一行包含一个整数 $t$，表示测试组数。

每组测试数据第一行包含一个整数 $n$，表示蛋糕长度。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各位置糖霜高度。

输出格式

对于每组测试数据，输出 $n$ 个整数，第 $i$ 个整数表示只考虑前 $i$ 个位置时可达到的最大平整高度。

数据范围

• $1 \le t \le 10^4$
• $2 \le n \le 2\cdot 10^5$
• $1 \le a_i \le 10^9$
• 所有测试数据的 $n$ 之和不超过 $2\cdot 10^5$

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 

提示

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

当 $i = 1$ 时，爱丽丝对数组 $[4]$ 所代表的蛋糕感兴趣。由于蛋糕已经平整，糖霜的最大高度为 $4$ 。

当 $i = 2$ 时，爱丽丝对数组 $[4, 2]$ 所代表的蛋糕感兴趣。如果爱丽丝将刀放在高度为 $4$ 的位置，得到的蛋糕上的糖霜高度为 $[4, 2]$ ，这样蛋糕就不会平整。但是，如果爱丽丝把刀放在高度为 $3$ 的位置，一个单位的糖霜就会从第一个位置推到第二个位置，这样得到的蛋糕的糖霜高度为 $[3, 3]$ ，也就是平整了。因此，在保持平整的情况下，糖霜的最大高度为 $3$ 。

当 $i = 3$ 时，如果爱丽丝将刀放在高度为 $4$ 的地方，那么得到的糖霜高度为 $[4, 2, 3]$ 。但是，如果爱丽丝把刀放在高度为 $3$ 的位置，得到的糖霜高度将是 $[3, 3, 3]$ 。因此，在保持平整的情况下，糖霜的最大高度是 $3$ 。

来源

Codeforces Round 2232 B - Cake Leveling