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