AT_arc149_b.[ARC149B] Two LIS Sum

对于数列 $P = (P_1, \ldots, P_N)$，我们记其最长严格递增子序列的长度为 $\mathrm{LIS}(P)$。

给定两个由 $1$ 到 $N$ 的整数构成的排列 $A = (A_1, \ldots, A_N)$ 和 $B = (B_1, \ldots, B_N)$。你可以对这两个数列进行如下操作任意多次（也可以一次都不做）：

• 选择一个整数 $1 \leq i \leq N-1$，交换 $A_i$ 与 $A_{i+1}$，同时交换 $B_i$ 与 $B_{i+1}$。

请你求出通过若干次操作后，$\mathrm{LIS}(A) + \mathrm{LIS}(B)$ 的最大可能值。

最长递增子序列的定义
数列的子序列是指，从原数列中删除 $0$ 个或多个元素后，按原顺序连接剩下元素得到的新数列。例如，$(10,30)$ 是 $(10,20,30)$ 的子序列，但 $(20,10)$ 不是 $(10,20,30)$ 的子序列。

数列的最长递增子序列是指所有严格递增的子序列中，长度最大的那一个。

输入通过标准输入给出，格式如下：

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

请输出通过若干次操作后，$\mathrm{LIS}(A) + \mathrm{LIS}(B)$ 的最大可能值。

数据范围

• $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$

样例解释 1

例如，可以按如下方式操作，使得 $\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

如果一次操作都不做，可以得到 $\mathrm{LIS}(A) + \mathrm{LIS}(B) = 10$。

由 ChatGPT 4.1 翻译