问题描述

对于一个序列 $P = (P_1, \ldots, P_N)$，记 $\mathrm{LIS}(P)$ 为最长递增子序列的长度。

给定排列 $A = (A_1, \ldots, A_N)$ 和 $B = (B_1, \ldots, B_N)$，它们包含了从 $1$ 到 $N$ 的整数。你可以对这些序列进行任意次数的以下操作（可能为零次）：

• 选择一个整数 $i$，满足 $1\leq i\leq N-1$。交换 $A_i$ 和 $A_{i+1}$，以及交换 $B_i$ 和 $B_{i+1}$。

找到使 $\\mathrm{LIS}(A) + \\mathrm{LIS}(B)$ 最大的可能结果。

什么是最长递增子序列？

一个序列的子序列是通过从原序列中删除零个或多个元素，并保持剩余元素的顺序连接而得到的序列。例如，$(10,30)$ 是 $(10,20,30)$ 的一个子序列，但是 $(20,10)$ 不是 $(10,20,30)$ 的一个子序列。

一个序列的最长递增子序列是该序列的一个子序列，其中最长递增子序列的长度在所有严格递增的子序列中最大。

约束条件

• $2\leq N\leq 3\times 10^5$
• $1\leq A_i\leq N$
• $1\leq B_i\leq N$
• 若 $i\neq j$，则 $A_i\neq A_j$ 且 $B_i\neq B_j$。

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $\ldots$ $A_N$ $B_1$ $\ldots$ $B_N$

输出

输出使 $\\mathrm{LIS}(A) + \\mathrm{LIS}(B)$ 最大的可能结果。

示例输入 1

5
5 2 1 4 3
3 1 2 5 4

示例输出 1

8

以下是使 $\\mathrm{LIS}(A) + \\mathrm{LIS}(B) = 8$ 的一种方法：

• 使用 $i = 2$ 进行操作。现在，$A = (5,1,2,4,3)$，$B = (3,2,1,5,4)$。
• 使用 $i = 1$ 进行操作。现在，$A = (1,5,2,4,3)$，$B = (2,3,1,5,4)$。
• 使用 $i = 4$ 进行操作。现在，$A = (1,5,2,3,4)$，$B = (2,3,1,4,5)$。

这里，$A$ 的最长递增子序列为 $(1,2,3,4)$，因此 $\\mathrm{LIS}(A)=4$，$B$ 的最长递增子序列为 $(2,3,4,5)$，因此 $\\mathrm{LIS}(B)=4$。

示例输入 2

5
1 2 3 4 5
1 2 3 4 5

示例输出 2

10

你可以选择不进行任何操作，使得 $\\mathrm{LIS}(A) + \\mathrm{LIS}(B) = 10$。