AT_awc0005_e 山の高さ調査

高橋君は登山ガイドとして働いており、ある山脈にある $ N $ 個の山の情報を管理しています。山には $ 1 $ から $ N $ までの番号が付けられており、 $ i $ 番目の山の標高は $ A_i $ メートルです（ $ 1 \leq i \leq N $ ）。 高橋君のもとには、観光客から $ Q $ 個の問い合わせが届きました。 $ j $ 番目（ $ 1 \leq j \leq Q $ ）の問い合わせでは、 $ L_j $ 番目から $ R_j $ 番目までの山が指定され、その中で最も標高が高い山の標高を知りたいという内容です。 各問い合わせに対して、指定された範囲の山の標高の最大値を求めてください。

> $ 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 $ 番目までの山の標高の最大値を出力せよ。

### 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) $ - 入力はすべて整数