{"problem":{"name":"射命丸文的取材之旅","description":{"content":"射命丸文现在收集到了 $2n$ 条新闻。她想要将其刊登于自己的报刊之上。然而，自己的报刊最多只能刊登 $n$ 条新闻。 为了能在 $n$ 条新闻的篇幅中让自己的报刊得到最大的吸引力，她将这 $2n$ 条新闻**等分**成**两份**，即每一份中均有 $n$ 条新闻。 每一条新闻自然有着其吸引力。在**第一份**中，第 $i$ 条新闻有着吸引力 $a_i$，而在**第二份**中，第 $i$ 条新","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8445"},"statements":[{"statement_type":"Markdown","content":"射命丸文现在收集到了 $2n$ 条新闻。她想要将其刊登于自己的报刊之上。然而，自己的报刊最多只能刊登 $n$ 条新闻。\n\n为了能在 $n$ 条新闻的篇幅中让自己的报刊得到最大的吸引力，她将这 $2n$ 条新闻**等分**成**两份**，即每一份中均有 $n$ 条新闻。\n\n每一条新闻自然有着其吸引力。在**第一份**中，第 $i$ 条新闻有着吸引力 $a_i$，而在**第二份**中，第 $i$ 条新闻有着吸引力 $b_i$。这两份新闻的划分在输入时已经给定。\n\n现在射命丸文要从中选取新闻放入自己的报刊。报刊上的第 $i$ 条新闻，将选择**第一份**新闻的第 $i$ 条或**第二份**新闻的第 $i$ 条。这样，报刊上的新闻就可以构成一个长度为 $n$ 的序列，第 $i$ 项也就是第 $i$ 条新闻有着吸引力 $c_i \\in \\{a_i,b_i\\}$。\n\n而这样的一份报刊有着其综合影响力。根据射命丸文的经验，对于她这样的一份含有 $n$ 条新闻的报刊，其综合影响力为：\n\n$$\\max\\{r-l+1-\\operatorname{mex}\\{c_l,c_{l+1},\\dots, c_{r-1},c_r\\}\\}(1\\le l\\le r\\le n)$$\n\n其中 $\\operatorname{mex}\\{c_l,c_{l+1},\\dots,c_{r-1},c_r\\}$ 指的是 $c_l,c_{l+1},\\dots,c_{r-1},c_r$ 中没有出现过的**最小非负整数**。\n\n现在她希望知道，在进行这些操作之后，自己的报刊的**最大**的综合影响力会是多少呢？由于她还要继续取材，因此她把这个任务交付给了你。\n\n【形式化题意】\n\n给定序列 $\\{a_n\\},\\{b_n\\}$，求一个序列 $\\{c_n\\}$ 满足 $\\forall i\\in[1,n],c_i\\in\\{a_i,b_i\\}$，最大化\n\n$$\\max\\{r-l+1-\\operatorname{mex}\\{c_l,c_{l+1},\\dots, c_{r-1},c_r\\}\\}(1\\le l\\le r\\le n)$$\n\n并输出该式子可能的最大值。\n\n## Input\n\n第一行一个正整数 $n$，表示**每一份**新闻中的新闻条数。\n\n第二行 $n$ 个**非负整数**表示第一份新闻中每一条新闻的吸引力，即 $a_1,a_2\\dots ,a_{n-1},a_n$。\n\n第三行 $n$ 个**非负整数**表示第二份新闻中每一条新闻的吸引力，即 $b_1,b_2\\dots ,b_{n-1},b_n$。\n\n## Output\n\n输出一个整数，表示报刊的**最大**的综合影响力会是多少。\n\n[samples]\n\n## Background\n\n射命丸文（Syameimaru Aya）是一只鸦天狗。她不定期制作名为「文文。新闻」的报纸，而为此，她需要对她收集到的新闻进行剪裁。\n\n## Note\n\n**【样例解释和说明】**\n\n射命丸文可以让自己的 $5$ 条新闻分别取第二份的第 $1$ 条，第一份的第 $2$ 条，第一份的第 $3$ 条，第一份的第 $4$ 条和第二份的第 $5$ 条。这样一来，她的报刊每条新闻的吸引力 $c_i$ 分别为 $0,1,0,1,0$。令 $l=1,r=5$，则 $\\operatorname{mex}\\{c_1,c_2,c_3,c_4,c_5\\}=2$，$r-l+1-\\operatorname{mex}\\{c_1,c_2,c_3,c_4,c_5\\}=3$，不难证明其为数列 $c$ 的综合影响力，也是**所有的可能的** $c$ 的最大综合影响力。\n\n**【数据范围】**\n\n对于 $20\\%$ 的数据，满足 $1 \\leq n\\leq 10$。\n\n另外 $40\\%$ 的数据满足 $a_i=b_i$。\n\n对于 $100\\%$ 的数据，满足 $1 \\leq n\\le 10^6$，$0\n\\leq a_i,b_i\\leq n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8445","tags":["洛谷原创","洛谷月赛"],"sample_group":[["5\n0 1 0 1 2\n0 2 0 1 0","3"]],"created_at":"2026-03-03 11:09:25"}}