#P1326E. Bombs
Bombs
Description
You are given a permutation, .
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, .
For each from to :
- Add to .
- If the -th position contains a bomb, remove the largest element in .
After the process is completed, will be non-empty. The cost of the configuration of bombs equals the largest element in .
You are given another permutation, .
For each , find the cost of a configuration of bombs such that there exists a bomb in positions .
For example, for , you need to find the cost of a configuration without bombs, and for , you need to find the cost of a configuration with bombs in positions .
The first line contains a single integer, ().
The second line contains distinct integers (.
The third line contains distinct integers (.
Print space-separated integers, such that the -th of them equals the cost of a configuration of bombs in positions .
Input
The first line contains a single integer, ().
The second line contains distinct integers (.
The third line contains distinct integers (.
Output
Print space-separated integers, such that the -th of them equals the cost of a configuration of bombs in positions .
Samples
Note
In the first test:
- If there are no bombs, is equal to at the end of the process, so the cost of the configuration is .
- If there is one bomb in position , is equal to at the end of the process, so the cost of the configuration is ;
- If there are two bombs in positions and , is equal to at the end of the process, so the cost of the configuration is .
In the second test:
Let's consider the process for . There are three bombs on positions , , and .
At the beginning, .
- Operation : Add to , so is equal to . There exists a bomb in position , so we should delete the largest element from . is equal to .
- Operation : Add to , so is equal to . There exists a bomb in position , so we should delete the largest element from . is equal to .
- Operation : Add to , so is equal to . There is no bomb in position , so we do nothing.
- Operation : Add to , so is equal to . There is no bomb in position , so we do nothing.
- Operation : Add to , so is equal to . There exists a bomb in position , so we delete the largest element from . Now, is equal to .
- Operation : Add to , so is equal to . There is no bomb in position , so we do nothing.
In the end, we have , so the cost of the configuration is equal to .