← 返回题目列表

AtCoder · awc0009_e

E. 温度波动调查

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

分数: 433 分

问题陈述

高桥正在气象观测站做兼职。他的工作是分析过去的温度数据。

天文台有以下温度记录 N 天。每一天的编号是从 1 to N,以及当天的温度 i 是 A_i ℃.

高桥的主管要求他调查规定时间内的温度波动范围。在这里, 温度波动范围 某一时期的 是指该时期内最高气温与最低气温之差。例如,如果周期只有 1 天,则波动范围为 给出了 0.

Q 查询。在 i- 第一个查询 (i = 1, 2, \ldots, Q),两个整数 已指定 L_i, R_i 。高桥必须确定并报告从一天开始的一段时间内的温度波动范围 L_i 到今天 R_i (含)。

对于每个查询,查找指定时间段内的温度波动范围。

约束

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • -10^9 \leq A_i \leq 10^9
  • 1 \leq L_i \leq R_i \leq N
  • 所有输入值均为整数

输入

N Q
A_1 A_2 \ldots A_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 第一行包含一个整数 N 表示天数和整数 Q 代表查询数量,以空格分隔。
  • 第二行包含 N 整数 A_1, A_2, \ldots, A_N 代表每天的温度,以空格分隔。
  • 的 i- 以下各项 Q 行 (i = 1, 2, \ldots, Q) 包含开始日期 L_i 和结束日 R_i 期间 i-第一个查询,以空格分隔。

输出

打印 Q 行。的 i- 第行 (i = 1, 2, \ldots, Q)应包含以下问题的答案 i第查询,即其中的最大值和最小值的差值 A_{L_i}, A_{L_i+1}, \ldots, A_{R_i},作为整数。


示例输入 1

5 3
20 18 25 22 19
1 3
2 5
4 4

示例输出 1

7
7
0

示例输入 2

7 5
-5 12 8 -3 15 7 10
1 7
3 6
1 2
2 4
5 7

示例输出 2

20
18
17
15
8

示例输入 3

10 8
1000000000 -1000000000 500 -200 300 0 999999999 -999999999 100 -100
1 2
1 10
3 6
7 8
5 5
2 8
4 9
1 1

示例输出 3

2000000000
2000000000
700
1999999998
0
1999999999
1999999998
0