CF1326E.Bombs

You are given a permutation, $p_1, p_2, \ldots, p_n$.

Imagine that some positions of the permutation contain bombs, such that there exists at least one position without a bomb.

For some fixed configuration of bombs, consider the following process. Initially, there is an empty set, $A$.

For each $i$ from $1$ to $n$:

• Add $p_i$ to $A$.
• If the $i$-th position contains a bomb, remove the largest element in $A$.

After the process is completed, $A$ will be non-empty. The cost of the configuration of bombs equals the largest element in $A$.

You are given another permutation, $q_1, q_2, \ldots, q_n$.

For each $1 \leq i \leq n$, find the cost of a configuration of bombs such that there exists a bomb in positions $q_1, q_2, \ldots, q_{i-1}$.

For example, for $i=1$, you need to find the cost of a configuration without bombs, and for $i=n$, you need to find the cost of a configuration with bombs in positions $q_1, q_2, \ldots, q_{n-1}$.

给你一个排列 $p_1, p_2, \ldots, p_n$。

设想该排列的某些位置上放置了炸弹，且至少存在一个位置没有炸弹。

对于某组固定的炸弹位置配置，考虑如下过程：初始时集合 $A$ 为空。

对每个 $i$ 从 $1$ 到 $n$ 执行以下操作：

• 将 $p_i$ 加入 $A$；
• 若第 $i$ 个位置上有炸弹，则从 $A$ 中移除最大元素。

该过程结束后，$A$ 非空。该炸弹配置的代价定义为此时 $A$ 中的最大元素。

你另被给定一个排列 $q_1, q_2, \ldots, q_n$。

对每个 $1 \leq i \leq n$，求满足如下条件的炸弹配置的代价：在位置 $q_1, q_2, \ldots, q_{i-1}$ 上均放置炸弹。

例如，当 $i=1$ 时，你需要计算无炸弹配置的代价；当 $i=n$ 时，你需要计算在位置 $q_1, q_2, \ldots, q_{n-1}$ 上均放置炸弹的配置的代价。

The first line contains a single integer, $n$ ($2 \leq n \leq 300\,000$).

The second line contains $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \leq p_i \leq n)$.

The third line contains $n$ distinct integers $q_1, q_2, \ldots, q_n$ ($1 \leq q_i \leq n)$.

第一行包含一个整数 $n$（$2 \leq n \leq 300\,000$）。

第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \ldots, p_n$（$1 \leq p_i \leq n$）。

第三行包含 $n$ 个互不相同的整数 $q_1, q_2, \ldots, q_n$（$1 \leq q_i \leq n$）。

Print $n$ space-separated integers, such that the $i$-th of them equals the cost of a configuration of bombs in positions $q_1, q_2, \ldots, q_{i-1}$.

输出 $n$ 个以空格分隔的整数，其中第 $i$ 个整数等于在位置 $q_1, q_2, \ldots, q_{i-1}$ 放置炸弹的配置的代价。

In the first test:

• If there are no bombs, $A$ is equal to ${1, 2, 3}$ at the end of the process, so the cost of the configuration is $3$.
• If there is one bomb in position $1$, $A$ is equal to ${1, 2}$ at the end of the process, so the cost of the configuration is $2$;
• If there are two bombs in positions $1$ and $2$, $A$ is equal to ${1}$ at the end of the process, so the cost of the configuration is $1$.

In the second test:

Let's consider the process for $i = 4$. There are three bombs on positions $q_1 = 5$, $q_2 = 2$, and $q_3 = 1$.

At the beginning, $A = {}$.

• Operation $1$: Add $p_1 = 2$ to $A$, so $A$ is equal to ${2}$. There exists a bomb in position $1$, so we should delete the largest element from $A$. $A$ is equal to ${}$.
• Operation $2$: Add $p_2 = 3$ to $A$, so $A$ is equal to ${3}$. There exists a bomb in position $2$, so we should delete the largest element from $A$. $A$ is equal to ${}$.
• Operation $3$: Add $p_3 = 6$ to $A$, so $A$ is equal to ${6}$. There is no bomb in position $3$, so we do nothing.
• Operation $4$: Add $p_4 = 1$ to $A$, so $A$ is equal to ${1, 6}$. There is no bomb in position $4$, so we do nothing.
• Operation $5$: Add $p_5 = 5$ to $A$, so $A$ is equal to ${1, 5, 6}$. There exists a bomb in position $5$, so we delete the largest element from $A$. Now, $A$ is equal to ${1, 5}$.
• Operation $6$: Add $p_6 = 4$ to $A$, so $A$ is equal to ${1, 4, 5}$. There is no bomb in position $6$, so we do nothing.

In the end, we have $A = {1, 4, 5}$, so the cost of the configuration is equal to $5$.

在第一个测试中：

• 如果没有炸弹，过程结束时 $A = \{1, 2, 3\}$，因此该配置的代价为 $3$；
• 如果在位置 $1$ 处有一颗炸弹，过程结束时 $A = \{1, 2\}$，因此该配置的代价为 $2$；
• 如果在位置 $1$ 和 $2$ 处各有一颗炸弹，过程结束时 $A = \{1\}$，因此该配置的代价为 $1$。

在第二个测试中：

考虑 $i = 4$ 时的过程。炸弹位于位置 $q_1 = 5$、$q_2 = 2$ 和 $q_3 = 1$。

初始时，$A = \{\}$。

• 操作 $1$：将 $p_1 = 2$ 加入 $A$，此时 $A = \{2\}$。位置 $1$ 处存在一颗炸弹，因此需从 $A$ 中删除最大元素，$A = \{\}$；
• 操作 $2$：将 $p_2 = 3$ 加入 $A$，此时 $A = \{3\}$。位置 $2$ 处存在一颗炸弹，因此需从 $A$ 中删除最大元素，$A = \{\}$；
• 操作 $3$：将 $p_3 = 6$ 加入 $A$，此时 $A = \{6\}$。位置 $3$ 处没有炸弹，因此不执行任何操作；
• 操作 $4$：将 $p_4 = 1$ 加入 $A$，此时 $A = \{1, 6\}$。位置 $4$ 处没有炸弹，因此不执行任何操作；
• 操作 $5$：将 $p_5 = 5$ 加入 $A$，此时 $A = \{1, 5, 6\}$。位置 $5$ 处存在一颗炸弹，因此需从 $A$ 中删除最大元素，此时 $A = \{1, 5\}$；
• 操作 $6$：将 $p_6 = 4$ 加入 $A$，此时 $A = \{1, 4, 5\}$。位置 $6$ 处没有炸弹，因此不执行任何操作。

最终，$A = \{1, 4, 5\}$，因此该配置的代价为 $5$。