CF2232B Cake Leveling

Alice 正在为她的派对准备一个蛋糕。但由于时间紧迫，蛋糕上的糖霜铺得不均匀。为了解决这个问题，Alice 决定将刀子放在某个整数高度，然后从左到右扫平糖霜，使糖霜铺得平整。 具体地，设第 $i$ 个位置的糖霜高度为 $a_i$。假设 Alice 将刀子放在某个整数高度 $h$。如果第 $i$ 个位置的糖霜高度大于 $h$，那么多余的糖霜会被推到第 $i+1$ 个位置。最后一个位置 $n$ 上多余的糖霜会被完全推出蛋糕之外。 Alice 和她的朋友们非常喜欢蛋糕上的糖霜。由于 Alice 可能只准备切下蛋糕的一部分（前缀），而不是整个蛋糕，请你帮她计算，对于每个 $i=1,2,\ldots,n$，若让蛋糕前 $i$ 个位置的糖霜高度都相等，糖霜最高能达到多少。

每个测试用例包含多组数据。第一行包含测试用例的数量 $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$），表示每个位置的糖霜高度。 所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

对于每个测试用例，输出 $n$ 个整数，第 $i$ 个整数表示在保证前 $i$ 个位置糖霜铺平的情况下，糖霜最高可以达到的高度。

第一个测试用例的解释如下： 当 $i=1$ 时，Alice 只考虑蛋糕的前 $[4]$ 这一部分，因为本来就已经平整，所以糖霜的最大高度为 $4$。 当 $i=2$ 时，考虑前 $[4, 2]$。如果 Alice 把刀放在高度 $4$，经过扫刀后的糖霜高度仍为 $[4, 2]$，不平整。但如果把刀放在高度 $3$，第一位多出的糖霜会推到第二位，最终糖霜高度变成 $[3, 3]$，达到了平整，因此最大高度为 $3$。 当 $i=3$ 时，如果刀子放在高度 $4$，经过处理后糖霜高度为 $[4, 2, 3]$，不平整。如果刀子放在高度 $3$，最终糖霜高度为 $[3, 3, 3]$，是平整的，所以最大高度为 $3$。 由 ChatGPT 5 翻译