/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 433 点
問題文
高橋君は気象観測所でアルバイトをしています。彼の仕事は、過去の気温データを分析することです。
観測所には N 日分の気温記録があります。各日には 1 から N までの番号が付けられており、i 日目の気温は A_i ℃でした。
高橋君は上司から、指定された期間内での気温の変動幅を調べるように頼まれました。ここで、ある期間の 気温の変動幅 とは、その期間内の気温の最大値と最小値の差のことを指します。例えば、期間が 1 日だけの場合、変動幅は 0 です。
Q 回の問い合わせが与えられます。i 番目（i = 1, 2, \ldots, Q）の問い合わせでは 2 つの整数 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
- 1 行目には、日数を表す整数 N と、問い合わせの回数を表す整数 Q が、スペース区切りで与えられる。
- 2 行目には、各日の気温を表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
- 続く Q 行の i 行目（i = 1, 2, \ldots, Q）には、i 番目の問い合わせの期間の開始日 L_i と終了日 R_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
Score : 433 pts
Problem Statement
Takahashi is working a part-time job at a weather observatory. His job is to analyze past temperature data.
The observatory has temperature records for N days. Each day is numbered from 1 to N, and the temperature on day i was A_i ℃.
Takahashi's supervisor asked him to investigate the temperature fluctuation range within specified periods. Here, the temperature fluctuation range of a certain period refers to the difference between the maximum and minimum temperatures within that period. For example, if the period consists of only 1 day, the fluctuation range is 0.
Q queries are given. In the i-th query (i = 1, 2, \ldots, Q), two integers L_i, R_i are specified. Takahashi must determine and report the temperature fluctuation range in the period from day L_i to day R_i (inclusive).
For each query, find the temperature fluctuation range within the specified period.
Constraints
- 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
- All input values are integers
Input
N Q A_1 A_2 \ldots A_N L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- The first line contains an integer N representing the number of days and an integer Q representing the number of queries, separated by a space.
- The second line contains N integers A_1, A_2, \ldots, A_N representing the temperature on each day, separated by spaces.
- The i-th of the following Q lines (i = 1, 2, \ldots, Q) contains the start day L_i and end day R_i of the period for the i-th query, separated by a space.
Output
Print Q lines. The i-th line (i = 1, 2, \ldots, Q) should contain the answer to the i-th query, that is, the difference between the maximum and minimum values among A_{L_i}, A_{L_i+1}, \ldots, A_{R_i}, as an integer.
Sample Input 1
5 3 20 18 25 22 19 1 3 2 5 4 4
Sample Output 1
7 7 0
Sample Input 2
7 5 -5 12 8 -3 15 7 10 1 7 3 6 1 2 2 4 5 7
Sample Output 2
20 18 17 15 8
Sample Input 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
Sample Output 3
2000000000 2000000000 700 1999999998 0 1999999999 1999999998 0