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

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

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