问题描述

小明与春娇是青梅竹马，常常腻在一起玩叠积木游戏。

他们平常玩的积木游戏如下：

他们有一些积木，每个积木大小可能不同，但高度都是$1$。

首先会把所有积木用随机的顺序堆成塔状。

不过堆成塔状时，当「任相邻的两个积木满足上方的积木大小刚好比下方的积木小 $1$」时堆出来的塔才好看。

所以接着他们就会把一些积木移除，没被移除的积木维持原来的顺序，使得堆出来的塔变得好看。

例如，若原本有 $5$ 个积木，由上到下依序大小为：$3, 2, 4, 3, 5$，那么我们可以把由上数来第 $2$ 个和第 $4$ 个积木移除，剩下的积木大小按照顺序就变为 $3, 4, 5$，如此一来就把塔从不好看变成好看了。但如是移除第 $1$ 个和第 $3$ 个积木，剩下的积木大小按照顺序就变为 $2, 3, 5$，当中的第 $2$ 个积木和第 $3$ 个积木大小关係就不满足整座塔好看的条件了，因为 $5$ 并不等于 $3 + 1$。

而积木堆得越高，好看的程度也越高，所以小明与春娇会在满足「任相邻的两个积木满足上方的积木大小刚好比下方的积木小 $1$」的情况下，把积木塔堆的尽可能高。

但是今年暑假，春娇要回老家度过三个月，不能再和小明一起玩耍了。不过小明与春娇这样子想：「就算我们分隔两地，但只要小明喝伯爵奶茶，春娇也喝伯爵奶茶；小明吃 oreo 巧克力，春娇也吃 oreo 巧克力，小明看墙壁上的向日葵挂画，春娇也看墙壁上的向日葵挂画；小明玩叠积木游戏，春娇也玩叠积木游戏。这样子我们就像每天都身在同一个地方，这就是我们保持友谊的方式！这就叫做量子纠缠友谊！

但是这当中有个问题：虽然他们都有伯爵奶茶 和 oreo 巧克力，墙壁上也都有向日葵挂画，但春娇老家的积木大小却和小明家的不一定一样，且他们初始时随机堆的积木顺序也可能不一样。

你可以只看下面的部分：

小明和春娇在玩叠积木游戏时，随机堆好积木后，会告知对自己堆好的积木 由上到下 每块积木的大小，并一起决定各自要移除哪些积木，使得他们两个人堆出来的两个积木塔满足：

1. 任相邻的两个积木满足上方的积木大小刚好比下方的积木小 $1$。
2. 长得 一模一样（指层数相同，且从上到下每一层的积木大小一样）。
3. 积木塔 尽可能地高。

若达成这些条件，他们就维持了 完美的量子纠缠友谊。

现在告诉你小明和春娇各自随机堆出来的积木塔初始时都有 $n$ 个积木，其中小明堆出来的积木塔 由上到下 的积木大小依次为 $a_1, a_2, \ldots, a_n$，春娇堆出来的积木塔 由上到下 依次为 $b_1, b_2, \ldots, b_n$。请大家帮小明和春娇计算，他们各自移除一些积木并满足 完美的量子纠缠友谊 时，堆出来的塔最高能有多高，请输出此高度，若没有任何一种高度大于 $0$ 的堆法，输出 $0$ 即可。

输入格式

输入共有 $3$ 行。

第一行有一个正整数 $n$。

第二行有 $n$ 个正整数 $a_1, a_2, \ldots, a_n$。

第三行有 $n$ 个正整数 $b_1, b_2, \ldots, b_n$。

输入的每行相邻两个数之间都恰有一个空白分隔。

所有输入都保证 $1 \le a_i, b_i \le n$。

输出格式

输出只有一行，包含一个非负的整数代表答案。

数据范围

对于 $30\%$ 的数据，$1 \le n \le 5000$，且对于所有 $i，a_i = b_i$。

对于 $60\%$ 的数据，$1 \le n \le 5000$。

对于全部数据，$1 \le n \le 2 \times 10^5$。

样例输入1

5
3 2 4 3 5
3 2 4 3 5

样例输出1

3

样例1解释

他们只需要各自移除从上数来第 $2$ 和第 $4$ 个积木就能使移除完后的积木塔满足完美的量子纠缠友谊，且高度最高。故答案为 $3$。

样例输入2

5
3 2 4 3 5
4 5 2 3 3

样例输出2

2

样例2解释

小明可以移除由上数来第 $1, 3, 5$ 个积木，而春娇移除由上数来第 $1, 2, 5$ 个积木，就能使移除完后的积木塔满足完美的量子纠缠友谊，且高度最高。故答案为 $2$。