Pawn Shop

You run a tight ship at the pawn shop. You arrange certain items in the window to be displayed to the street. You sometimes display the same type of item multiple times. For simplicity, we think of the items on display as a sequence of values, where each value is the type of item being shown.

For example, your display could be this sequence:

$1, 2, 6, 2, 7, 9, 8, 5$

After coming back from your latest vacation, you find that your staff has completely rearranged the display by moving items around. Yikes! For example, the display above could be rearranged to:

$2, 6, 1, 2, 9, 7, 5, 8$

You fear this could cause confusion and scare off repeat customers. But you do not have time to move items back to their original positions.

As a compromise, you will put dividers up in the window to partition the displayed items into groups of consecutive items. Each group must be a rearrangement of the item types that were in those positions in your preferred arrangement.

More precisely, let $a_1, \ldots, a_N$ denote the first sequence and $b_1, \ldots, b_N$ denote the second sequence. You may place dividers around $i, i+1, \ldots, j$ if $b_i, b_{i+1}, \ldots, b_j$ is a rearrangement of $a_i, a_{i+1}, \ldots, a_j$. You do not need to put a divider at the beginning or end of the sequence. If $a_i = b_i$, then a group may be formed using just this single index $i$.

With the sequences above, you could place dividers # at three positions as shown here:

2 6 1 # 2 # 7 9 # 5 8

It is not possible to divide the sequence into more than four groups that have this property.

Given the two sequences, determine how to partition the new sequence into the maximum possible number of groups.

The first line of input contains a single integer $N$ ($1 \leq N \leq 300\,000$), the length of the two sequences.

The next line contains $N$ integers $a_1, \ldots, a_N$ ($1 \leq a_i \leq 10^9$), the original sequence.

The next line contains $N$ integers $b_1, \ldots, b_N$ ($1 \leq b_i \leq 10^9$), the rearranged sequence. The values $b_1, \ldots, b_N$ are a rearrangement of the values $a_1, \ldots, a_N$.

Display the rearranged sequence with a valid partition using dividers (#) that yields the maximum number of groups.

If there are multiple possible solutions, you may display any of them.