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$ 个查询，其形式如下：

给定满足 $s_i \neq t_i$ 的整数 $s_i, t_i$（$1 \leq s_i, t_i \leq N$）。判断在图 $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$ 行，若顶点 $s_i$ 到顶点 $t_i$ 的路径存在，则输出其最小权重；否则输出 -1。

约束条件

• $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$
• 输入中的所有值均为整数

样例解释 1

图 $G$ 包含以下 4 条无向边：$\lbrace 1, 3 \rbrace$、$\lbrace 2, 3 \rbrace$、$\lbrace 2, 4 \rbrace$、$\lbrace 3, 4 \rbrace$。

• 对于第 1 个查询，存在路径 $1 \to 3 \to 4$，其权重为 $W_1 + W_3 + W_4 = 5 + 4 + 2 = 11$，为最小可能值。
• 对于第 2 个查询，存在路径 $4 \to 3$，其权重为 $W_4 + W_3 = 2 + 4 = 6$，为最小可能值。
• 对于第 3 个查询，顶点 5 到顶点 2 之间不存在路径，因此输出 -1。

翻译由 DeepSeek R1 完成