历史

题目描述

某款竞技游戏会记录玩家每天的积分变化。

玩家连续进行了 n 天比赛，第 i 天结束后，系统会保存当天获得的积分：

a[i]

为了分析玩家的成长情况，系统会进行 q 次历史数据查询。

每次查询给出一个整数：

x

表示查看玩家在第 x 天结束时的历史最高积分。

历史最高积分定义为：

从第 1 天开始，到第 x 天为止，玩家曾经获得过的最高积分。

即：

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

请你输出每次查询对应的结果。

---

输入格式

第一行输入一个整数：

n

表示游戏记录的天数。

第二行输入 n 个整数：

a1 a2 ... an

表示玩家每天结束后的积分。

第三行输入一个整数：

q

表示查询次数。

接下来 q 行，每行输入一个整数：

x

表示查询第 x 天结束时的历史最高积分。

---

输出格式

对于每一次查询，输出一个整数：

表示从第 1 天到第 x 天之间出现过的最高积分。

每个答案占一行。

---

数据范围

1 ≤ n ≤ 100000
1 ≤ q ≤ 100000
0 ≤ a[i] ≤ 1000000
1 ≤ x ≤ n

---

输入样例

7
5 8 3 10 6 9 12
3
5
7
3

---

输出样例

10
12
8

---

样例解释

玩家积分记录：

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

 5     8     3    10     6     9    12

---

查询：

第一次查询

x = 5

查看前 5 天：

5 8 3 10 6

最高积分：

10

---

第二次查询

x = 7

查看全部记录：

5 8 3 10 6 9 12

最高积分：

12

---

第三次查询

x = 3

查看前三天：

5 8 3

最高积分：

8

测试点编号	n 上界	q 上界	难度层级	数据特征	覆盖点与设计目的
1, 2	1	5	弱数据	单元素、重复查询	覆盖最小规模、初始化、同一位置多次查询
3	5	6		严格递增	检查每一步都由当前输入值接管
4		5		严格递减	检查 mx[i-1]-1 的连续传递
5	6	8	正常数据	全相同	检查衰减后被 a[i] 重新抬升
6, 7	9	11		低谷、高峰、零值混合	覆盖峰值传播、低谷衰减、中间位置查询
8	10			查询乱序且重复	防止误以为查询单调
9	50	16	正常偏强	周期峰值、交替小值	卡只做普通前缀最大或只输出原数组的错误做法
10	12			接近 10^9 的大值	检查大整数范围内的衰减与比较
11	1000	20	极限预备	较大规模、周期峰值	检查线性预处理、数组下标和多点查询
12	100000	13	极限数据	n=100000、稀疏大峰值	检查数组容量、时间复杂度和端点查询