B. Wifi Password
time limit per test
8 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Robi is the greatest technician who ever lived. He came to visit his friend Aritro's house, where Aritro was proudly showing off his new Wi-Fi connection. Robi also wanted to test it, but asking Aritro for the Wi-Fi password would be far too ordinary for a technician of his caliber. Using his special software, Robi found the password; however, he still had to solve the puzzle given by the system to access it.

Robi has discovered two arrays of $$$n$$$ integers, $$$A$$$ and $$$B$$$. You can perform the following operation at most once:

  • Choose an index $$$i$$$ ($$$0 \le i \le n$$$) and swap $$$A[i]$$$ and $$$B[i]$$$.
For an array $$$A$$$, let $$$\text{MEX}(A)$$$ denote the smallest non-negative integer that does not appear in $$$A$$$.

For two arrays $$$A$$$ and $$$B$$$ of the same length, define

$$$$$$F(A, B) = \min|\text{MEX}(A) - \text{MEX}(B)|$$$$$$

where the minimum is taken over all possible ways of performing the operation above, including not performing any swap. In other words, $$$F(A, B)$$$ is the smallest possible gap between the two $$$\text{MEX}$$$ values that you can achieve by performing at most one swap.

Robi must compute, for every prefix length from $$$1$$$ to $$$n$$$, the value $$$F$$$ for that prefix. That is, for each $$$k$$$ ($$$1 \le k \le n$$$), he needs to do the following:

$$$$$$F\big(A[0 \dots k-1],\; B[0 \dots k-1]\big).$$$$$$

In other words, he must compute the function for every prefix of the arrays. For each prefix, the difference between the two $$$\text{MEX}$$$ values must be minimized.

Each prefix is evaluated independently; a swap performed for one prefix does not affect any other prefix.

Help Robi solve the puzzle!

Constraints

  • $$$1 \le n \le 2 \times 10^5$$$
  • $$$0 \le A[i], B[i] \le n$$$
Input
  • Line 1: A single integer $$$n$$$ representing the size of the array.
  • Line 2: $$$n$$$ space-separated integers representing the elements of array $$$A$$$.
  • Line 3: $$$n$$$ space-separated integers representing the elements of array $$$B$$$.
Output
  • Line 1: $$$n$$$ space-separated integers representing the answer
Scoring

Subtasks

SubtaskPointsAdd. constraints
$$$1$$$$$$5$$$$$$n=10, A[i]=B[i]$$$
$$$2$$$$$$15$$$$$$A[i]$$$ is even
$$$3$$$$$$15$$$$$$ n \le 1000$$$
$$$4$$$$$$20$$$$$$ n \le 5000$$$
$$$5$$$$$$45$$$No additional constraints
Examples
Input
5
0 1 2 3 4
0 1 1 2 3
Output
0 0 1 1 1
Input
4
0 4 2 2
1 1 0 2
Output
1 1 1 0
Note

$$$\text{MEX}(A)$$$ is defined as the smallest non-negative integer that is not present in the array. For example, $$$\text{MEX}([1,2,0,5])$$$ is $$$3$$$, and $$$\text{MEX}([1,2,4,9])$$$ is $$$0$$$.

In the second example, for every index $$$i$$$, we compute as follows:

  • $$$i=0$$$: $$$A=[0]$$$, $$$B=[1]$$$. $$$\text{MEX}(A)=1$$$ and $$$\text{MEX}(B)=0$$$, so the answer is $$$|1-0|=1$$$.
  • $$$i=1$$$: $$$A=[0,4]$$$, $$$B=[1,1]$$$. $$$\text{MEX}(A)=1$$$ and $$$\text{MEX}(B)=0$$$, so the answer is $$$|1-0|=1$$$.
  • $$$i=2$$$: $$$A=[0,4,2]$$$, $$$B=[1,1,0]$$$. $$$\text{MEX}(A)=1$$$ and $$$\text{MEX}(B)=2$$$, so the answer is $$$|1-2|=1$$$.
  • $$$i=3$$$: $$$A=[0,4,2,2]$$$, $$$B=[1,1,0,2]$$$. Here index $$$1$$$ was swapped, so $$$A$$$ becomes $$$[0,1,2,2]$$$ and $$$B$$$ becomes $$$[1,4,0,2]$$$. Now $$$\text{MEX}(A)=3$$$ and $$$\text{MEX}(B)=3$$$, so the answer is $$$|3-3|=0.$$$