P14676 [ICPC 2025 Seoul R] Mex Culpa

Due to variations in the performance of the evaluation system, an additional 2 seconds of time limit is provided for this problem.

The **mex** (shorthand for *minimum excluded value*) of a sequence is the smallest non-negative integer that is not in the sequence. For example: - $\text{mex}(\{\}) = 0$ - $\text{mex}(\{1,2,3\}) = 0$ - $\text{mex}(\{5,0,1,1,4\}) = 2$ - $\text{mex}(\{0,5,2,1,5,0,1,2\}) = 3$ While the mex function has applications in combinatorial game theory, it is still a rather niche method for mapping a sequence to an integer. In the absence of a more organic problem, we have repurposed this concept to construct a task of a somewhat artificial nature. Sorry! Write a program that, given two sequences of positive integers $a = [a_1, a_2, \cdots, a_n]$ and $b = [b_1, b_2, \cdots, b_n]$, evaluates the following recurrence: for $1 \le i \le n$, $$ f_i = \text{mex}(\{f_j \mid 1 \le j \le i-1; a_i \le a_j + b_j; a_j \le a_i + b_i\}) $$

Your program is to read from standard input. The first line contains a single integer, $n$ ($1 \le n \le 250,000$), representing the length of the sequences. The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le 10^9$) representing the sequence $a$. The third line contains $n$ positive integers $b_1, b_2, \cdots, b_n$ ($1 \le b_i \le 10^9$), representing the sequence $b$.

Your program is to write to standard output. Print exactly one line consisting of $n$ space-separated integers, denoting $f_1, f_2, \cdots, f_n$.