题目描述

数列 $P\ =\ (P_1,\ \ldots,\ P_N)$ に対し，その最長増加部分列の長さを $\mathrm{LIS}(P)$ と書くことにします．

$1$ 以上 $N$ 以下の整数からなる順列 $A\ =\ (A_1,\ \ldots,\ A_N)$ および $B\ =\ (B_1,\ \ldots,\ B_N)$ が与えられます．これらの数列に対して，以下の操作を何度でも行うことができます（$0$ 回でもよいです）．

• $1\leq\ i\leq\ N-1$ となる整数 $i$ をひとつ選ぶ．$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)$ としてありうる最大値を出力してください．

题目大意

给定长为 $n$ 的两排列 $A,B$，允许进行操作：

选择 $1 \leq i \leq n-1$，将 $A_i,B_i$ 同时与 $A_{i+1},B_{i+1}$ 交换。

求二者 $\text{LIS}$ 最大和。

5
5 2 1 4 3
3 1 2 5 4

8

5
1 2 3 4 5
1 2 3 4 5

10

提示

制約

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

Sample Explanation 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$ が成り立ちます．

Sample Explanation 2

操作を $1$ 度も行わないことにより，$\mathrm{LIS}(A)\ +\ \mathrm{LIS}(B)\ =\ 10$ を達成できます．