AT_arc193_a [ARC193A] Complement Interval Graph

整数 $ l, r $ に対し、 $ l $ 以上 $ r $ 以下の整数全体からなる集合を $ [l, r] $ で表します。 すなわち、 $ [l, r] = \lbrace l, l+1, l+2, \ldots, r-1, r\rbrace $ です。 $ N $ 組の整数のペア $ (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N) $ が与えられます。 これに対して、下記で定義される無向グラフ $ G $ を考えます。 - $ 1, 2, \ldots, N $ と番号付けられた $ N $ 個の頂点を持つ。 - すべての $ i, j \in [1, N] $ について次が成り立つ： $ [L_i, R_i] $ と $ [L_j, R_j] $ の共通部分が空であるとき、かつ、そのときに限り、頂点 $ i $ と頂点 $ j $ の間に無向辺が張られている。 また、 $ i = 1, 2, \ldots, N $ について、頂点 $ i $ の重みを $ W_i $ で定めます。 $ G $ に関する $ Q $ 個のクエリが与えられるので、それらを与えられる順に処理してください。 $ i = 1, 2, \ldots, Q $ について、 $ i $ 番目のクエリは下記の通りです。 > $ s_i \neq t_i $ を満たす $ 1 $ 以上 $ N $ 以下の整数 $ s_i, t_i $ が与えられる。 $ G $ において、頂点 $ s_i $ から頂点 $ t_i $ へのパスが存在するかを判定せよ。 存在する場合は、そのようなパスの**重み**の最小値を出力せよ。 ここで、頂点 $ s $ から頂点 $ t $ へのパスの重みは、パス上の頂点（両端点である頂点 $ s $ と頂点 $ t $ を含む）の重みの総和で定義されます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ W_1 $ $ W_2 $ $ \cdots $ $ W_N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $ $ Q $ $ s_1 $ $ t_1 $ $ s_2 $ $ t_2 $ $ \vdots $ $ s_Q $ $ t_Q $

$ Q $ 行出力せよ。 $ i = 1, 2, \ldots, Q $ について、 $ i $ 行目には、 頂点 $ s_i $ から頂点 $ t_i $ へのパスが存在する場合はそのようなパスの重みの最小値を出力し、存在しない場合は `-1` を出力せよ。

### Sample Explanation 1 $ G $ は $ \lbrace 1, 3\rbrace, \lbrace 2, 3\rbrace, \lbrace 2, 4\rbrace, \lbrace 3, 4\rbrace $ の $ 4 $ 本の無向辺を持つグラフです。 - $ 1 $ 番目のクエリに関して、頂点 $ 1 $ から頂点 $ 4 $ への $ 1 \to 3 \to 4 $ というパスが存在します。そのパスの重みは $ W_1 + W_3 + W_4 = 5 + 4 + 2 = 11 $ であり、これが考えられる最小値です。 - $ 2 $ 番目のクエリに関して、頂点 $ 4 $ から頂点 $ 3 $ への $ 4 \to 3 $ というパスが存在します。そのパスの重みは $ W_4 + W_3 = 2 + 4 = 6 $ であり、これが考えられる最小値です。 - $ 3 $ 番目のクエリに関して、頂点 $ 5 $ から頂点 $ 2 $ へのパスは存在しません。したがって、`-1` を出力します。 ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq W_i \leq 10^9 $ - $ 1 \leq L_i \leq R_i \leq 2N $ - $ 1 \leq s_i, t_i \leq N $ - $ s_i \neq t_i $ - 入力はすべて整数