历史最高温度

题目描述

气象研究中心连续记录了 n 天的气温变化。

第 i 天的最高温度记录为：

a[i]

为了分析近期天气变化，研究人员希望知道：

截至第 i 天为止，出现过的最高温度是多少。

也就是说，对于每一天 i，需要输出：

$\max(a_1,a_2,...,a_i)$

请你帮助气象研究中心完成统计。

---

输入格式

第一行输入一个整数：

n

表示记录的天数。

第二行输入 n 个整数：

a1 a2 ... an

表示每天记录的最高温度。

---

输出格式

输出 n 个整数：

第 i 个整数表示：

从第 1 天到第 i 天出现过的最高温度。

每个结果之间用空格隔开。

---

数据范围

1 ≤ n ≤ 100000
-50 ≤ a[i] ≤ 50

---

输入样例

6
12 15 9 20 18 25

---

输出样例

12 15 15 20 20 25

---

样例解释

每天温度记录：

第1天 第2天 第3天 第4天 第5天 第6天

 12    15    9    20    18    25

统计过程：

第1天：

最高温度 = 12

第2天：

max(12,15)=15

第3天：

max(12,15,9)=15

第4天：

max(12,15,9,20)=20

第5天：

max(12,15,9,20,18)=20

第6天：

max(12,15,9,20,18,25)=25

因此输出：

12 15 15 20 20 25

---

注意事项

1. 第 i 天的答案包含当天温度。
2. 不能每一天都重新遍历之前所有天数，否则时间复杂度较高。
3. 需要保存之前计算出的最高温度。

---

测试点编号	n ≤	特殊性质	覆盖点与设计目的
1		最小规模	检查初始化与首个输出
2, 3	2	两元素	分别覆盖前一项衰减更大、当前值更大
4	5	严格递减	检查 mx[i-1]-1 == x[i] 的边界相等
5	6	单峰衰减	首项大、后续小，检查连续传播
6		全相同	检查重复值与稳定输出
7		含负数和 0	覆盖负数输入、跨 0 刷新
8		高低交错	多次刷新与衰减交替
9	7	大整数	接近 int 范围的大数、极小数混合
10	10⁵	极限规模	检查线性处理和大输出规模