← 返回题目列表

Codeforces · 1172/A

A. Nauuo 和卡片

中文机器翻译题面 查看原题

Nauuo是一个喜欢打牌的女孩。

有一天,她在打牌,却发现牌中混杂着一些空牌。

有$$$n$$$卡,编号从$$$1$$$到$$$n$$$,并且与另外$$$n$$$空卡混合在一起。她把 $$$2n$$$ 卡片堆起来,并抽出了 $$$n$$$ 卡片。 Nauuo手中的$$$n$$$卡牌给出。一堆中剩余的 $$$n$$$ 卡牌也按照从上到下的顺序给出。

在一次操作中,她可以选择手中的一张牌并打出它 - 将其放在牌堆的底部,然后从牌堆中抽出顶部的牌。

Nauuo 想要尽快将 $$$n$$$ 编号的卡片按递增顺序堆叠起来(这堆从上到下第 $$$i$$$ 的卡片是卡片 $$$i$$$)。你能告诉她最少的手术次数吗?

输入

第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — 编号卡片的数量。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le n$$$) — Nauuo 手中的初始牌。 $$$0$$$ 代表一张空卡。

第三行包含 $$$n$$$ 整数 $$$b_1,b_2,\ldots,b_n$$$ ($$$0\le b_i\le n$$$) — 牌堆中的初始牌,按从上到下的顺序给出。 $$$0$$$ 代表一张空卡。

保证从 $$$1$$$ 到 $$$n$$$ 的每个数字在 $$$a_{1..n}$$$ 或 $$$b_{1..n}$$$ 中恰好出现一次。

输出

输出包含一个整数 - 使 $$$n$$$ 编号的卡片按升序堆积起来的最小操作数。

示例

输入 #1

3
0 2 0
3 0 1

输出 #1

2

输入 #2

3
0 2 0
1 0 3

输出 #2

4

输入 #3

11
0 0 0 5 0 0 0 4 0 0 11
9 2 6 0 8 1 7 0 3 0 10

输出 #3

18

注意

示例 1

我们可以在第一次操作中打出$$$2$$$牌并抽出$$$3$$$牌。之后,我们手里有$$$[0,3,0]$$$,牌堆里的牌从上到下是$$$[0,1,2]$$$。

然后,我们在第二次操作中打出$$$3$$$ 牌。堆里的牌是$$$[1,2,3]$$$,其中牌是按照递增的顺序堆起来的。

示例 2

打出一张空牌并抽出$$$1$$$牌,然后按顺序打出$$$1$$$、$$$2$$$、$$$3$$$。