给你一个排列,$$$p_1, p_2, \ldots, p_n$$$。
想象一下,排列的某些位置包含炸弹,这样至少存在一个位置没有炸弹。
对于一些固定配置的炸弹,请考虑以下过程。最初,有一个空集 $$$A$$$。
对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$:
- 将 $$$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}$$$位置有炸弹的配置的成本。
输入
第一行包含一个整数 $$$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)$$$。
输出
打印 $$$n$$$ 以空格分隔的整数,使得其中第 $$$i$$$ 等于在 $$$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
注意
在第一个测试中:
- 如果没有炸弹,$$$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$$$。