Bombs

题意翻译

给定两个长度均为 $n$ 的排列 $p,q$ 。对一个初始为空的集合 $s$ 进行如下操作：对于每个 $i$ ，将 $p_i$ 放入集合；如果 $i$ 被**标记**了，则此时再将集合中最大的数删除。求 $n$ 次操作后集合中最大的数。 排列 $q$ 的意义是，对于每个 $i$ ，询问将 $q_1,q_2\cdots q_{i-1}$ 都标记之后的上述操作的结果。 $1\leq n\leq 300,000$。

题目描述

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} $ .

输入输出格式

输入格式

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) $ .

输出格式

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} $ .

输入输出样例

输入样例 #1

3
3 2 1
1 2 3

输出样例 #1

3 2 1

输入样例 #2

6
2 3 6 1 5 4
5 2 1 4 6 3

输出样例 #2

6 5 5 5 4 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 $ .

题意翻译

给定两个长度均为 $n$ 的排列 $p,q$ 。对一个初始为空的集合 $s$ 进行如下操作：对于每个 $i$ ，将 $p_i$ 放入集合；如果 $i$ 被**标记**了，则此时再将集合中最大的数删除。求 $n$ 次操作后集合中最大的数。 排列 $q$ 的意义是，对于每个 $i$ ，询问将 $q_1,q_2\cdots q_{i-1}$ 都标记之后的上述操作的结果。 $1\leq n\leq 300,000$。