問題
長さ $N$ の数列 $A \ (a_1,a_2,\ldots,a_N)$ が与えられます。
以下のような $Q$ 回の質問に答えてください。
- $j \ (1 \leq j \leq Q)$ 番目の質問： $A$ の $1$ 番目から $R_j$ 番目までの要素のなかで、最も値の小さい要素の値はいくつか。
入力
入力は以下の形式で標準入力から与えられる。
$N \ Q$ $a_1 \ a_2 \ \ldots \ a_N$ $R_1$ $R_2$ $\vdots$ $R_Q$
出力
出力は $Q$ 行からなる。
$j$ 行目には $j$ 番目の質問の答えを出力せよ。
なお、出力は改行区切りで行うこと。
制約
- $1 \leq N,Q \leq 2 \times 10^5$
- $-10^9 \leq a_i \leq 10^9 \ (1 \leq i \leq N)$
- $1 \leq R_j \leq N$
- 入力は全て整数。
部分点
- $1 \leq N,Q \leq 10^3$ 満たすケースに全て正解した場合、$10$ 点が与えられる。
- 追加制約のないケースに全て正解した場合、追加で $20$ 点が与えられ、合計で $30$ 点が得られる。
入出力例
入力例１
5 3 4 5 0 4 -3 3 1 5
出力例１
0 4 -3
$1$ 番目の質問について解説します。
数列 $A$ の $1$ 番目から $4$ 番目までの要素のなかで、最も値の小さい要素は $3$ 番目の要素です。よって $3$ 番目の要素の値である $0$ を出力します。
このケースは部分点の制約 $(1 \leq N,Q \leq 10^3)$ を満たします。