← 返回题目列表

AtCoder · awc0005_e

E. 山地高度测量

中文机器翻译题面 查看原题

分数: 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