OUPC2025 OPENコンテスト 2026/03/29 09:00 ~ 2026/03/29 14:00 5:00:00.000

I Dual Array Swap

問題
制限時間: 1.5 sec メモリ制限: 1024 MB
Dual Array Swap
Statement

長さ \(N\) の \(2\) つの整数列 \(A=(A_1,A_2,\dots, A_N)\) と \(B=(B_1, B_2, \dots, B_N)\) が与えられます。

あなたは以下の \(3\) つの操作を好きな順番で好きな回数行うことができます。

  • 操作1: \(1\le i \lt j \le N\) を満たす整数 \(i,j\) を選び、\(A_i\) と \(A_j\) の値を入れ替える。
  • 操作2: \(1\le i \lt j \le N\) を満たす整数 \(i,j\) を選び、\(B_i\) と \(B_j\) の値を入れ替える。
  • 操作3: \(1\le i \le N\) を満たす整数 \(i\) を選び、\(A_i\) と \(B_i\) の値を入れ替える。

\(A_i \le B_i\) がすべての \(i~(1\le i \le N)\) について満たされるようにするために必要な操作回数の最小値を求めてください。

Input

入力は以下の形式で標準入力から与えられます。

\(N\)
\(A_1~A_2~\dots~A_N\)
\(B_1~B_2~\dots~B_N\)

入力は以下の制約をすべて満たします。

  • \(2\le N \le 2\times 10^5\)
  • \(1\le A_i \le 10^9\)
  • \(1\le B_i \le 10^9\)
  • 入力はすべて整数

Output

答えを一行に出力してください。

Scoring

以下の追加制約を満たすデータセットに正解した場合、部分点が与えられます。

  • (10点): \(N = 2\)
  • (10点): \(i=2,3,\dots,N\) について、\(A_i=A_1\) かつ \(B_i=B_1\)
  • (80点): 追加制約なし

Examples

Input 1
3
1 4 5
6 3 2
Output 1
2
Input 2
3
1 2 3
4 5 6
Output 2
0
Input 3
2
2 2
1 2
Output 3
1
Input 4
3
8 8 8
4 4 4
Output 4
3

Note

入出力例 \(1\) について、例えば以下のように操作をすると、\(2\) 回の操作で条件を満たすことができます。

  • \(A_1\) と \(A_2\) を入れ替えます。操作後の数列は \(A=(4,1,5),B=(6,3,2)\) です。
  • \(A_3\) と \(B_3\) を入れ替えます。操作後の数列は \(A=(4,1,2),B=(6,3,5)\) です。
\(1\) 回の操作で条件を満たすことはできないため、答えは \(2\) です。

入出力例 \(2\) については初期状態ですでに条件を満たしています。

入出力例 \(3\) について、入力は一つ目の追加制約を満たします。

入出力例 \(4\) について、入力は二つ目の追加制約を満たします。

サンプル