Maximizing Newspaper Influence

Sho‐Myo Marbun has collected \(2n\) news items and wants to publish exactly \(n\) of them in her newspaper. The \(2n\) news items are initially divided into two parts, each containing \(n\) items. In the first part, the \(i\)-th news item has an attractiveness of \(a_i\), and in the second part, the \(i\)-th news item has an attractiveness of \(b_i\) (\(1 \le i \le n\)).

She will form her newspaper by choosing one news item from each index \(i\) (i.e. for the \(i\)-th slot, she may choose either \(a_i\) or \(b_i\)), thus obtaining a sequence \(\{c_i\}_{i=1}^{n}\) where \(c_i \in \{a_i, b_i\}\). The overall influence of the newspaper is defined as:

[ \max_{1 \le l \le r \le n} \Bigl{ (r-l+1) - \operatorname{mex}{c_l, c_{l+1}, \dots, c_r} \Bigr} ]

Here, for a given set \(S\), \(\operatorname{mex}(S)\) is the smallest non-negative integer that is not present in \(S\). For example, \(\operatorname{mex}\{1,3\}=0\) and \(\operatorname{mex}\{0,1,3\}=2\). Your task is to choose \(c_1, c_2, \dots, c_n\) optimally so that the overall influence is maximized, and to output the maximum possible value.

Observation: Notice that if at some position \(i\) at least one of \(a_i\) or \(b_i\) is nonzero, we can choose a nonzero value to avoid adding a \(0\) into that position. Let an index be called "free" if \(a_i \neq 0\) or \(b_i \neq 0\) (so that we can avoid placing a \(0\)), and "forced" if both \(a_i\) and \(b_i\) are \(0\). This choice affects the \(\operatorname{mex}\) of any contiguous segment in the final sequence. In particular:

• If all \(n\) positions are free, we can choose all \(c_i\) nonzero and get \(\operatorname{mex} = 0\) for the entire sequence. Hence, the influence is \(n\).
• If there is at least one forced index, then no matter what we do, the entire sequence will contain at least one \(0\) (from the forced positions). By carefully choosing the free positions (avoiding the number \(1\) if possible), we can ensure that \(\operatorname{mex} = 1\) for the entire sequence, yielding an influence of \(n-1\). It can be shown that this is optimal even when considering subsegments.

Therefore, the answer is:

[ \text{answer} = \begin{cases} n, & \text{if every index is free (i.e. there is no forced index)}\ n - 1, & \text{otherwise} \end{cases} ]

You are given \(n\), and two sequences \(a_1, a_2, \dots, a_n\) and \(b_1, b_2, \dots, b_n\). Output the maximum possible overall influence.

inputFormat

The input consists of three lines:

1. The first line contains a single integer \(n\) \( (1 \leq n \leq 10^5)\).
2. The second line contains \(n\) integers: \(a_1, a_2, \dots, a_n\).
3. The third line contains \(n\) integers: \(b_1, b_2, \dots, b_n\).

outputFormat

Output a single integer—the maximum possible overall influence achievable.

sample

3
1 0 0
0 2 0

2