Sparse Table 練習問題 3 Ruby編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
ポスト
下記の問題をプログラミングしてみよう！
長さ N の数列 A が与えられます。
ここで、数列の要素を 0-index で表すとします。
つまり、数列 A は A_0, A_1, ..., A_{N-1} です。
Q 個のクエリが与えられるので順に解答してください。クエリの形式は以下の通りです。
・l r：A_l, A_{l+1}, ..., A_{r-1} で 2 番目に小さい値を出力する。ただし、r - l ≧ 2 を満たすことが保証されます。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N Q
A_0 A_1 ... A_{N-1}
l_1 r_1
l_2 r_2
...
l_Q r_Q
・1 行目には、数列の長さを表す整数 N とクエリの数を表す整数 Q が与えられます。
・2 行目には、数列 A が空白区切りで与えられます。
・続く Q 行の i 行目には i 個目のクエリが与えられます。クエリの形式は問題文の通りです。
・入力は合計で Q+2 行からなり、入力値最終行の末尾に改行が１つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
期待する出力は Q 行からなります。
i 行目には i 個目のクエリに対する答えを出力してください。
最後は改行し、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・1 ≦ N ≦ 10^5
・1 ≦ Q ≦ 10^5
・1 ≦ A_i ≦ 10^9
・0 ≦ l_i < r_i ≦ N
・r_i - l_i ≧ 2
- 入力例1
-
5 5
14 12 17 10 7
3 5
1 5
3 5
1 5
0 4
- 出力例1
-
7
7
7
7
10
- 入力例2
-
10 8
87 43 82 67 15 29 26 46 26 91
2 9
3 6
8 10
7 10
1 7
0 7
3 5
3 10
- 出力例2
-
26
15
26
26
15
26
15
26
- 入力例3
-
20 10
798310957 408203102 907806154 754326295 333502312 382488679 385892024 564217183 770499401 859706508 881505918 793083479 216505095 769760065 366257958 312830386 894283498 535995685 569181956 324629782
5 8
5 7
11 18
6 9
0 18
1 14
1 17
18 20
4 18
4 10
- 出力例3
-
385892024
382488679
312830386
564217183
216505095
333502312
216505095
324629782
312830386
382488679
- 入力例4
-
5 3
5 5 5 5 5
1 4
0 3
0 5
- 出力例4
-
5
5
5
