区間の最大値-中級 R(Beta)編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
整数 N, D, K と、 長さ N の配列 A = [A_1, A_2, ..., A_N] および K 個のクエリが与えられます。
1 つのクエリにつき、整数 L, R が与えられます。
各クエリについて、配列 A の L 番目から R 番目までの要素のうち最大であるものの値を出力してください。
ただし、N = D * D であることが保証されます。
また、R は常に D の倍数であることが、L は {D の倍数 + 1} であることが保証されます。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N D K
A_1
A_2
.
.
.
A_N
L_1 R_1
L_2 R_2
L_3 R_3
.
.
.
L_K R_K
* 1 行目では、配列 A の要素数 N、D、およびクエリの個数 K がこの順に空白区切りで与えられます。
* 続く N 行では、配列 A の要素が先頭から順に与えられます。
* 続く K 行では、クエリとして L_i, R_i が、この順に空白区切りで 1 行に 1 組与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
各クエリについて、配列 A の L_i 番目から R_i 番目までの要素のうち最大であるものの値を出力してください。
出力の最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
* 2 ≦ N ≦ 10000
* N = D * D
* 1 ≦ K ≦ 100000
* 1 ≦ L_i ＜ R_i ≦ N
* -100000 ≦ A_i ≦ 100000
* N, R_i は D の倍数
* L_i は {D の倍数 + 1}
* 入力は合計で N + K + 1 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
- 入力例1
-
9 3 2
-35445
-6905
37616
74640
98019
6105
84222
44425
81045
1 3
7 9
- 出力例1
-
37616
84222
- 入力例2
-
25 5 4
-93245
-98216
-42525
67051
50283
51223
53773
17862
-21372
-3624
-26266
-2983
79285
-83983
-78154
-32547
82947
-72825
92888
41186
16957
68187
23961
-16922
67352
1 25
1 20
16 25
6 10
- 出力例2
-
92888
92888
92888
53773
