Card Flipping 2

Time limit2sMemory limit1024 MB

Summary

Each card i flips every later card j whose top face is smaller than card i's top face. Print the final top face of each card.

Level: Medium7 of 10
Topics: Segment tree, Simulation, Array
Solved: No attempts yet

Problem

Card Flipping 1 and 2 are different problems.

Junwon has $N$ cards. Each card has an integer from $1$ to $N$ written on each side. Junwon lays the $N$ cards in a row. The integers on the top faces are $a_1,a_2,\cdots ,a_N$ , and the integers on the bottom faces are $b_1,b_2,\cdots ,b_N$ .

Junwon increases $i$ from $1$ to $N$ by $1$ each time and repeats the following action.

Compare the $i$ -th card with the $j$ -th card for $i<j\le N$ . Let $X$ and $Y$ be the integers on the top faces of the $i$ -th and $j$ -th cards. Flip every $j$ -th card that satisfies $X>Y$ .

After all actions are finished, find the integer on the top face of each card.

Input

The first line contains an integer $N$ ( $2\le N\le 200\,000$ ).

The second line contains the integers $a_1,a_2,\cdots ,a_N$ ( $1\le a_i\le N$ ), separated by spaces.

The third line contains the integers $b_1,b_2,\cdots ,b_N$ ( $1\le b_i\le N$ ), separated by spaces.

Output

After all actions are finished, print the integer on the top face of each card, separated by spaces.

Examples2

Example 1
Input
```
4
1 2 3 4
4 3 2 1
```
Expected output
```
1 2 3 4
```
Example 2
Input
```
5
3 1 4 2 4
2 3 2 5 1
```
Expected output
```
3 3 4 5 1
```