分数: 433 分
问题陈述
高桥担任登山向导并管理有关 N 山脉中的山脉。山脉的编号是从 1 to N,以及 i第一座山是 A_i 米 (1 \leq i \leq N).
高桥已收到 Q 游客询问。的 j- 第一个查询 (1 \leq j \leq Q) 指定来自 L_j-第 R_j-th,并要求其中最高的海拔。
对于每个查询,查找指定范围内山脉的最大海拔。
约束
- 1 \leq N \leq 10^5
- 1 \leq Q \leq 10^5
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq L_j \leq R_j \leq N (1 \leq j \leq Q)
- 所有输入均为整数
输入
N Q A_1 A_2 \ldots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- 第一行包含一个整数 N 代表山脉的数量和一个整数 Q 代表查询数量,以空格分隔。
- 第二行包含整数 A_1, A_2, \ldots, A_N 代表每座山的海拔,以空格分隔。
- A_i 代表海拔高度(以米为单位) i第一座山。
- 如下 Q 行, j- 第行 (1 \leq j \leq Q,这是 (2 + j)-整个输入的第行)包含左端点 L_j 和右端点 R_j 指定的范围 j-第一个查询,以空格分隔。
输出
输出 Q 行。的 j- 第行 (1 \leq j \leq Q)应包含以下问题的答案 j第次查询,即从 L_j-第 R_j-th。
示例输入 1
5 3 100 250 180 320 150 1 3 2 5 4 4
示例输出 1
250 320 320
示例输入 2
8 5 1500 2300 1800 3776 2500 1200 2800 1900 1 8 3 6 1 4 5 8 2 2
示例输出 2
3776 3776 3776 2800 2300
示例输入 3
15 10 500 1200 800 3500 2200 1800 4200 900 3100 2700 1500 4800 2000 3300 1100 1 15 1 7 7 12 10 15 3 5 6 10 12 12 1 1 8 14 5 9
示例输出 3
4800 4200 4800 4800 3500 4200 4800 500 4800 4200