配点 : $500$ 点

問題文

数列 $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)$ としてありうる最大値を答えてください．

制約

• $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)$ としてありうる最大値を出力してください．

5
5 2 1 4 3
3 1 2 5 4

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

5
1 2 3 4 5
1 2 3 4 5

10

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