P8445 Aya Shameimaru's Material-Gathering Trip

Aya Shameimaru (Syameimaru Aya) is a crow tengu. She publishes a newspaper called “Bunbunmaru Newspaper” from time to time, and for that she needs to edit the news she has collected.

Aya Shameimaru has now collected $2n$ pieces of news. She wants to publish them in her newspaper. However, her newspaper can publish at most $n$ pieces of news. To make her newspaper as attractive as possible within $n$ pieces of news, she **evenly splits** these $2n$ pieces of news into **two parts**, so that each part contains $n$ pieces of news. Each piece of news naturally has an attractiveness value. In the **first part**, the $i$-th piece of news has attractiveness $a_i$, and in the **second part**, the $i$-th piece of news has attractiveness $b_i$. This partition into the two parts is already given in the input. Now Aya Shameimaru wants to choose news to put into her newspaper. For the $i$-th piece of news in the newspaper, she will choose either the $i$-th news from the **first part** or the $i$-th news from the **second part**. In this way, the news in the newspaper forms a sequence of length $n$, where the $i$-th item (the $i$-th piece of news) has attractiveness $c_i \in \{a_i,b_i\}$. Such a newspaper has an overall impact. According to Aya’s experience, for a newspaper containing $n$ pieces of news, its overall impact is: $$\max\{r-l+1-\operatorname{mex}\{c_l,c_{l+1},\dots, c_{r-1},c_r\}\}(1\le l\le r\le n)$$ Here, $\operatorname{mex}\{c_l,c_{l+1},\dots,c_{r-1},c_r\}$ means the **smallest non-negative integer** that does not appear among $c_l,c_{l+1},\dots,c_{r-1},c_r$. Now she wants to know: after doing these operations, what is the **maximum** possible overall impact of her newspaper? Since she still needs to continue gathering materials, she hands this task to you. 【Formal Problem Statement】 Given sequences $\{a_n\}$ and $\{b_n\}$, find a sequence $\{c_n\}$ such that $\forall i\in[1,n],c_i\in\{a_i,b_i\}$, maximizing $$\max\{r-l+1-\operatorname{mex}\{c_l,c_{l+1},\dots, c_{r-1},c_r\}\}(1\le l\le r\le n)$$ and output the maximum possible value of the expression.

The first line contains a positive integer $n$, representing the number of news items in **each** part. The second line contains $n$ **non-negative integers** representing the attractiveness of each piece of news in the first part, i.e. $a_1,a_2\dots ,a_{n-1},a_n$. The third line contains $n$ **non-negative integers** representing the attractiveness of each piece of news in the second part, i.e. $b_1,b_2\dots ,b_{n-1},b_n$.

Output one integer, representing the **maximum** possible overall impact of the newspaper.

**【Sample Explanation and Notes】** Aya Shameimaru can choose, for her $5$ news items, respectively: the 1st from the second part, the 2nd from the first part, the 3rd from the first part, the 4th from the first part, and the 5th from the second part. Then the attractiveness values $c_i$ of the news in her newspaper are $0,1,0,1,0$. Let $l=1,r=5$, then $\operatorname{mex}\{c_1,c_2,c_3,c_4,c_5\}=2$, and $r-l+1-\operatorname{mex}\{c_1,c_2,c_3,c_4,c_5\}=3$. It is not hard to prove that this is the overall impact of the sequence $c$, and it is also the maximum overall impact among **all possible** sequences $c$. **【Constraints】** For $20\%$ of the testdata, $1 \leq n\leq 10$. Another $40\%$ of the testdata satisfies $a_i=b_i$. For $100\%$ of the testdata, $1 \leq n\le 10^6$, $0 \leq a_i,b_i\leq n$. Translated by ChatGPT 5