CF2232B.Cake Leveling

Alice is preparing a cake for her party. However, she is in a rush, so the frosting on the cake is uneven. To quickly solve this issue, Alice will put her knife at some integer height and then sweep the frosting from left to right to make the frosting level.

Formally, let $a_i$ be the height of the frosting at the $i$-th position. Suppose that Alice puts her knife at some integer height $h$. If the height of frosting at position $i$ is greater than $h$, the excess frosting will be pushed to position $i + 1$. Excess frosting on position $n$ will be pushed off the cake completely.

Alice and her friends really love cake frosting. Since Alice might decide to serve some prefix of the cake instead of the whole cake, help her find the maximum height the frosting can be while keeping the frosting level for the first $i$ positions for $i = 1, 2, \ldots, n$.

Alice 正在为她的派对准备蛋糕。然而，她时间紧迫，因此蛋糕上的糖霜厚度不均匀。为了快速解决这一问题，Alice 将把她的刀片置于某个整数高度处，然后从左到右刮过糖霜，使糖霜表面变得平整。

形式化地，设 $a_i$ 表示第 $i$ 个位置处糖霜的高度。假设 Alice 将刀片置于某个整数高度 $h$ 处。若第 $i$ 个位置的糖霜高度大于 $h$，则超出 $h$ 的多余糖霜将被推至第 $i + 1$ 个位置；位于第 $n$ 个位置的多余糖霜则会完全被推出蛋糕之外。

Alice 和她的朋友们都非常喜爱蛋糕上的糖霜。由于 Alice 可能决定只提供蛋糕的某个前缀部分（而非整块蛋糕），请帮她求出：对于每个 $i = 1, 2, \ldots, n$，在保证前 $i$ 个位置糖霜高度完全相等的前提下，糖霜所能达到的最大高度。

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 an integer $n$ ($2 \leq n \leq 2\cdot 10^5$) — the length of Alice's cake.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq 10^9$) — the height of the frosting at the $i$-th position.

The sum of $n$ over all test cases is at most $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2\cdot 10^5$）—— 表示爱丽丝蛋糕的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_i \leq 10^9$）—— 表示第 $i$ 个位置上的糖霜高度。

所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, output $n$ integers where the $i$-th integer represents the maximum height the frosting can be while keeping the frosting level for the first $i$ positions.

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

The explanation of the first test case is as follows:

When $i = 1$, Alice is interested in the cake represented by an array $[4]$. Since the cake is already leveled, the maximum height the frosting can be is $4$.

When $i = 2$, Alice is interested in the cake represented by an array $[4, 2]$. If Alice put her knife at height $4$, the resulting cake will have a frosting of height $[4, 2]$, making the cake not levelled. However, if Alice put her knife at height $3$, one unit of frosting will be pushed from the first position to the second position, making the resulting cake have a frosting height of $[3, 3]$, which is leveled. Therefore, the maximum height the frosting can be while keeping it levelled is $3$.

When $i = 3$, if Alice put her knife at height $4$, the resulting frosting level will be $[4, 2, 3]$. However, if Alice put her knife at height $3$, the resulting frosting level will be $[3, 3, 3]$. Therefore, the maximum height the frosting can be while keeping it levelled is $3$.

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

当 $i = 1$ 时，Alice 关注的是由数组 $[4]$ 表示的蛋糕。由于该蛋糕已处于水平状态，糖霜所能达到的最大高度为 $4$。

当 $i = 2$ 时，Alice 关注的是由数组 $[4, 2]$ 表示的蛋糕。若 Alice 将刀片置于高度 $4$ 处，则所得蛋糕的糖霜高度为 $[4, 2]$，蛋糕未达水平状态。然而，若 Alice 将刀片置于高度 $3$ 处，则第一位置将有 1 单位糖霜被推至第二位置，使得最终蛋糕的糖霜高度变为 $[3, 3]$，此时蛋糕处于水平状态。因此，在保持蛋糕水平的前提下，糖霜所能达到的最大高度为 $3$。

当 $i = 3$ 时，若 Alice 将刀片置于高度 $4$ 处，则所得糖霜高度为 $[4, 2, 3]$；而若将刀片置于高度 $3$ 处，则所得糖霜高度为 $[3, 3, 3]$。因此，在保持蛋糕水平的前提下，糖霜所能达到的最大高度为 $3$。