A - Complement Interval Graph Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

整数 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 を含む）の重みの総和で定義されます。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

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 を出力せよ。

入力例 1

5
5 1 4 2 2
2 4
1 2
7 8
4 5
2 7
3
1 4
4 3
5 2

出力例 1

11
6
-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 を出力します。

入力例 2

8
44 75 49 4 78 79 12 32
5 13
10 16
6 8
6 15
12 15
5 7
1 15
1 2
5
5 6
3 2
7 5
4 5
5 4

出力例 2

157
124
-1
114
114

Score : 700 points

Problem Statement

For integers l, r, let [l, r] denote the set of all integers from l through r. That is, [l, r] = \lbrace l, l+1, l+2, \ldots, r-1, r\rbrace.

You are given N pairs of integers (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N). Based on these pairs, consider an undirected graph G defined as follows:

  • It has N vertices numbered 1, 2, \ldots, N.
  • For all i, j \in [1, N], there is an undirected edge between vertices i and j if and only if the intersection of [L_i, R_i] and [L_j, R_j] is empty.

In addition, for each i = 1, 2, \ldots, N, define the weight of vertex i to be W_i.

You are given Q queries about G. Process these queries in the order they are given. For each i = 1, 2, \ldots, Q, the i-th query is the following:

You are given integers s_i and t_i (both between 1 and N, inclusive) such that s_i \neq t_i. Determine whether there exists a path from vertex s_i to vertex t_i in G. If it exists, print the minimum possible weight of such a path.

Here, the weight of a path from vertex s to vertex t is defined as the sum of the weights of the vertices on that path (including both endpoints s and t).

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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print Q lines. For each i = 1, 2, \ldots, Q, on the i-th line, if there exists a path from vertex s_i to vertex t_i, print the minimum possible weight of such a path, and print -1 otherwise.

Sample Input 1

5
5 1 4 2 2
2 4
1 2
7 8
4 5
2 7
3
1 4
4 3
5 2

Sample Output 1

11
6
-1

G is a graph with four undirected edges: \lbrace 1, 3\rbrace, \lbrace 2, 3\rbrace, \lbrace 2, 4\rbrace, \lbrace 3, 4\rbrace.

  • For the first query, there is a path from vertex 1 to vertex 4 given by 1 \to 3 \to 4. The weight of this path is W_1 + W_3 + W_4 = 5 + 4 + 2 = 11, and this is the minimum possible.
  • For the second query, there is a path from vertex 4 to vertex 3 given by 4 \to 3. The weight of this path is W_4 + W_3 = 2 + 4 = 6, and this is the minimum possible.
  • For the third query, there is no path from vertex 5 to vertex 2. Hence, print -1.

Sample Input 2

8
44 75 49 4 78 79 12 32
5 13
10 16
6 8
6 15
12 15
5 7
1 15
1 2
5
5 6
3 2
7 5
4 5
5 4

Sample Output 2

157
124
-1
114
114