Range MinPair Query

2 secs 1024 MB

問題文

ともに長さ $N$ の数列 $A,B$ が与えられます。
$Q$ 個のクエリに答えてください。
各クエリでは $2$ つの整数 $l,r$ が与えられるので、 $l \le x \le y \le r$ を満たす整数の組 $(x,y)$ における $A_x+B_y$ の最小値を求めてください。

入力

入力は以下の形式で標準入力から与えられます。
$l_i,r_i$ $(1 \le i \le Q)$ は $i$ 番目のクエリにおける $l,r$ です。

$N\\$ $A_1$ $A_2$ $\cdots$ $A_N\\$ $B_1$ $B_2$ $\cdots$ $B_N\\$ $Q\\$ $l_1$ $r_1\\$ $l_2$ $r_2\\$ $\vdots\\$ $l_Q$ $r_Q$

入力は以下の制約を満たします。

値はすべて整数
$1 \le N,Q \le 10^5$
$1 \le A_i,B_i \le 10^8$
$1 \le l_i \le r_i \le N$

出力

各クエリについて、答えを出力して改行してください。

入力例

入力例1

出力例1

10
10

入力例2

出力例2

200000000

入力例3

10
314159 26535 89793 23846 26433 83279 50288 41971 69399 37510
58209 74944 59230 78164 6286 20899 86280 34825 34211 70679
8
1 4
1 7
2 2
2 6
2 10
4 8
5 6
7 10

出力例3

提出

登録なしで提出できます。

Go (1.21)