蛋糕抹平AI (CI翻译)
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.
Alice 正在为派对准备蛋糕。但她时间紧迫，蛋糕上的糖霜涂得不均匀。为了快速解决这个问题，Alice 会把刀放在某个整数高度，然后从左向右刮动糖霜，使糖霜变得平整。AI (CI翻译)
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.
形式化地，令 $a_i$ 表示第 $i$ 个位置的糖霜高度。假设 Alice 将刀放在某个整数高度 $h$。如果位置 $i$ 的糖霜高度大于 $h$，多出的糖霜就会被推到位置 $i + 1$。位置 $n$ 多出的糖霜会被完全推离蛋糕。AI (CI翻译)
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 可能决定只提供蛋糕的某个前缀，而不是整块蛋糕，请你对于 $i = 1, 2, \ldots, n$，求出使前 $i$ 个位置的糖霜保持平整时，糖霜可能达到的最大高度。AI (CI翻译)
Input
输入格式
AI (CI翻译)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.
每个测试包含多组测试用例。第一行包含测试用例数 $t$ ($1 \le t \le 10^4$)。接下来是各测试用例的描述。AI (CI翻译)
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.
每个测试用例的第一行包含一个整数 $n$ ($2 \leq n \leq 2\cdot 10^5$)，表示 Alice 的蛋糕长度。AI (CI翻译)
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.
每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ($1 \leq a_i \leq 10^9$)，表示第 $i$ 个位置的糖霜高度。AI (CI翻译)
The sum of $n$ over all test cases is at most $2 \cdot 10^5$.
所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。AI (CI翻译)
Output
输出格式
AI (CI翻译)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$ 个位置的糖霜保持平整时，糖霜可能达到的最大高度。AI (CI翻译)
Note
说明
AI (CI翻译)The explanation of the first test case is as follows:
第一个测试用例的解释如下：AI (CI翻译)
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$.
当 $i = 1$ 时，Alice 关注的蛋糕可表示为数组 $[4]$。由于蛋糕已经平整，糖霜可能达到的最大高度为 $4$。AI (CI翻译)
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$.
当 $i = 2$ 时，Alice 关注的蛋糕可表示为数组 $[4, 2]$。如果 Alice 将刀放在高度 $4$ 处，最终的糖霜高度仍为 $[4, 2]$，蛋糕并不平整。然而，如果 Alice 将刀放在高度 $3$ 处，第一处的一单位糖霜会被推到第二处，使最终的糖霜高度变为 $[3, 3]$，蛋糕因此变得平整。所以，使糖霜保持平整时可能达到的最大高度为 $3$。AI (CI翻译)
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 = 3$ 时，如果 Alice 将刀放在高度 $4$ 处，最终的糖霜高度为 $[4, 2, 3]$。但如果 Alice 将刀放在高度 $3$ 处，最终的糖霜高度为 $[3, 3, 3]$。所以，使糖霜保持平整时可能达到的最大高度为 $3$。AI (CI翻译)
样例
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
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。