Prefix and Suffix Mex
Limits: 2 sec., 512 MiB
For a sequence X composed of a finite number of non-negative integers, we define mex(X) as the smallest non-negative integer not in X. For example, mex(0,0,1,3)=2,mex(1)=0,mex()=0.
You are given two sequences b and c of n non-negative integers.
Construct a sequence a of n non-negative integers that satisfies all of the following conditions.
mex(a1,a2,…,ai)=bi for all 1≤i≤n.
mex(ai,ai+1,…,an)=ci for all 1≤i≤n.
It is guaranteed that for a given input such a sequence exists.
Input
The first line contains an integer n.
The second line contains n integers bi.
The third line contains n integers ci.
Output
Print n integers ai – the elements of sequence a. The values ai must not be greater than 109. One can prove that there exists a sequence satisfying this constraint.
If there are multiple answers, any of them will be accepted.
Constraints
1≤n≤105,
0≤bi,ci≤n,
it is guaranteed that there exists a sequence a satisfying the conditions.
Samples
Input (stdin) | Output (stdout) |
---|---|
4 1 1 1 3 3 3 2 0 | 0 2 0 1 |
Input (stdin) | Output (stdout) |
---|---|
7 0 0 3 4 4 4 4 4 4 4 4 3 2 0 | 1 2 0 3 2 0 1 |
Input (stdin) | Output (stdout) |
---|---|
4 0 0 0 0 0 0 0 0 | 4 7 74 474747474 |
Notes
In the first example, we have b=(1,1,1,3),c=(3,3,2,0). Let us show that the sequence a=(0,2,0,1) is a possible answer.
mex(a1)=mex(0)=1=b1.
mex(a1,a2)=mex(0,2)=1=b2.
mex(a1,a2,a3)=mex(0,2,0)=1=b3.
mex(a1,a2,a3,a4)=mex(0,2,0,1)=3=b4.
mex(a1,a2,a3,a4)=mex(0,2,0,1)=3=c1.
mex(a2,a3,a4)=mex(2,0,1)=3=c2.
mex(a3,a4)=mex(0,1)=2=c3.
mex(a4)=mex(1)=0=c4.
Thus, since all the conditions are met, a=(0,2,0,1) is an answer to the problem.