CF1583G Omkar and Time Travel

El Psy Kongroo。 Omkar 正在观看 Steins;Gate。 在 Steins;Gate 中，冈部伦太郎需要完成 $n$ 个任务（$1 \leq n \leq 2 \cdot 10^5$）。不幸的是，他并不知道这些任务需要在什么时候完成。 最初，时间为 $0$。之后将会按照以下规则发生时间旅行： - 对于每个 $k = 1, 2, \ldots, n$，冈部会在时间 $b_k$ 意识到他本应在时间 $a_k$ 完成第 $k$ 个任务（$a_k < b_k$）。 - 当他意识到这一点时，如果第 $k$ 个任务已经在时间 $a_k$ 完成，冈部就会让时间正常流逝。否则，他会穿越回时间 $a_k$ 并立即完成该任务。 - 如果冈部穿越回时间 $a_k$，那么所有在此之后完成的任务都会变为未完成。也就是说，对于每个 $j$，如果 $a_j > a_k$，那么第 $j$ 个任务如果已经完成，则会变为未完成（如果本来就是未完成，则不变）。 - 冈部记性不好，所以他只能在刚刚到达时间 $b_k$ 并得知自己本应在 $a_k$ 完成第 $k$ 个任务时，立即穿越回 $a_k$。也就是说，即使冈部之前已经需要完成第 $k$ 个任务，他在再次得知这个信息之前也不会记得。 请参考题目下方的样例说明以了解时间旅行的具体过程。 存在一个任务集合 $s$，当且仅当集合 $s$ 中的所有任务首次同时完成时（无论其它任务当前是否完成），就会发生一个有趣的场景。Omkar 很喜欢这个场景，他想知道在这个场景发生之前，冈部一共进行了多少次时间旅行。请输出这个次数对 $10^9 + 7$ 取模的结果。可以保证最终所有 $n$ 个任务都会被完成，因此答案一定存在。

第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示冈部需要完成的任务数。 接下来 $n$ 行，每行包含两个整数 $a_k$ 和 $b_k$（$1 \leq a_k < b_k \leq 2n$），分别表示第 $k$ 个任务需要完成的时间和冈部得知这一信息的时间。所有 $2n$ 个时间都是不同的（即从 $1$ 到 $2n$ 的每个时间恰好出现一次）。 接下来一行包含一个整数 $t$（$1 \leq t \leq n$），表示会触发有趣场景的任务集合 $s$ 的大小。 最后一行包含 $t$ 个整数 $s_1, s_2, \ldots, s_t$（$1 \leq s_k \leq n$，$s_1, s_2, \ldots, s_t$ 互不相同），表示任务集合 $s$。

输出一个整数，表示在集合 $s$ 中所有任务首次同时完成之前，冈部一共进行了多少次时间旅行，对 $10^9 + 7$ 取模。

对于第一个样例，所有任务都需要完成才能触发有趣场景。 最初时间为 $0$。在时间 $3$ 之前什么都不会发生，此时冈部意识到他应该在时间 $2$ 完成第 $2$ 个任务，于是他穿越回时间 $2$ 并完成该任务。 由于该任务现在已经完成，当时间再次来到 $3$ 时，他不会再次穿越。然而，在时间 $4$ 时，他会穿越回时间 $1$ 去完成第 $1$ 个任务。 这会导致第 $2$ 个任务变为未完成。这意味着此时第 $2$ 个任务尚未完成，因此有趣场景不会发生，尽管第 $1$ 个任务已经完成且冈部之前也完成过第 $2$ 个任务。 当时间再次来到 $3$ 时，他会再次穿越回时间 $2$ 并完成第 $2$ 个任务。 此时所有任务都已完成，冈部一共穿越了 $3$ 次。 第二个样例中，冈部需要完成的任务与第一个样例相同。但这次只需要第一个任务完成即可触发有趣场景。从上述过程可以看出，这会在冈部穿越了 $2$ 次后发生。 由 ChatGPT 4.1 翻译