E - Mountain Height Survey Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は登山ガイドとして働いており、ある山脈にある N 個の山の情報を管理しています。山には 1 から N までの番号が付けられており、i 番目の山の標高は A_i メートルです（1 \leq i \leq N）。

高橋君のもとには、観光客から Q 個の問い合わせが届きました。j 番目（1 \leq j \leq Q）の問い合わせでは、L_j 番目から R_j 番目までの山が指定され、その中で最も標高が高い山の標高を知りたいという内容です。

各問い合わせに対して、指定された範囲の山の標高の最大値を求めてください。

制約

  • 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
  • 1 行目には、山の個数を表す整数 N と、問い合わせの個数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各山の標高を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • A_i は i 番目の山の標高（メートル）を表す。
  • 続く Q 行のうち j 行目（1 \leq j \leq Q、入力全体では 2 + j 行目）には、j 番目の問い合わせで指定される範囲の左端 L_j と右端 R_j が、スペース区切りで与えられる。

出力

Q 行出力せよ。j 行目（1 \leq j \leq Q）には、j 番目の問い合わせに対する答え、すなわち L_j 番目から R_j 番目までの山の標高の最大値を出力せよ。

入力例 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

Score : 433 pts

Problem Statement

Takahashi works as a mountain guide and manages information about N mountains in a mountain range. The mountains are numbered from 1 to N, and the elevation of the i-th mountain is A_i meters (1 \leq i \leq N).

Takahashi has received Q queries from tourists. The j-th query (1 \leq j \leq Q) specifies the mountains from the L_j-th to the R_j-th, and asks for the highest elevation among them.

For each query, find the maximum elevation among the mountains in the specified range.

Constraints

  • 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)
  • All inputs 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 mountains and an integer Q representing the number of queries, separated by a space.
  • The second line contains integers A_1, A_2, \ldots, A_N representing the elevations of each mountain, separated by spaces.
  • A_i represents the elevation (in meters) of the i-th mountain.
  • In the following Q lines, the j-th line (1 \leq j \leq Q, which is the (2 + j)-th line of the entire input) contains the left endpoint L_j and the right endpoint R_j of the range specified by the j-th query, separated by a space.

Output

Output Q lines. The j-th line (1 \leq j \leq Q) should contain the answer to the j-th query, that is, the maximum elevation among the mountains from the L_j-th to the R_j-th.

Sample Input 1

5 3
100 250 180 320 150
1 3
2 5
4 4

Sample Output 1

250
320
320

Sample Input 2

8 5
1500 2300 1800 3776 2500 1200 2800 1900
1 8
3 6
1 4
5 8
2 2

Sample Output 2

3776
3776
3776
2800
2300

Sample Input 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

Sample Output 3

4800
4200
4800
4800
3500
4200
4800
500
4800
4200