Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Bombs

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

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

Input

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

Output

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

Examples

Input

3 3 2 1 1 2 3

Output

3 2 1

Input

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

Output

6 5 5 5 4 1

Note

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

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/18/2020 14:58:55 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|