クラスには $N$ 人の生徒がいる。各生徒には現在のクラス順位に基づいて $0$ から $N - 1$ までの番号が割り当てられている。すなわち、生徒 $i$ ($0 \le i \le N - 1$) は現在クラス順位 $i$ である。ここで、順位 $0$ が最も良く、順位 $N-1$ が最も悪い。

最近、英語と数学の試験が行われた。生徒 $i$ ($0 \le i \le N - 1$) の英語の順位は $A[i]$、数学の順位は $B[i]$ であった。$A$ と $B$ は長さ $N$ の順列である。

長さ $N$ の順列とは何か？ この問題において、長さ $N$ の順列 $P$ とは、すべての $0 \leq i \leq N - 1$ に対して $0 \leq P[i] \leq N-1$ を満たし、かつすべての $0 \leq i < j \leq N - 1$ に対して $P[i] \neq P[j]$ を満たす長さ $N$ の配列のことである。例えば、$[2,1,0]$ は長さ $3$ の順列であるが、$[1,2,3]$ や $[2,0,2]$ は長さ $3$ の順列ではない。

教師は生徒の順位を付け直したいと考えている。新しい順位は順列 $P$ で表すことができる。

各生徒 $i$ について、新しいクラス順位は以下の条件の少なくとも一方を満たさなければならない。

• $P[j] < P[i]$ を満たすすべての $j$ について、生徒 $j$ は英語において生徒 $i$ より順位が良い ($A[j] < A[i]$)、または
• $P[j] < P[i]$ を満たすすべての $j$ について、生徒 $j$ は数学において生徒 $i$ より順位が良い ($B[j] < B[i]$)。

警告 この条件は $P[j] < P[i]$ を満たす $j$ に対してのみ適用される。$P[j] \geq P[i]$ を満たす $j$ に対しては制約はない。各生徒 $i$ は、条件が満たされているかを評価する際、まず教科を一つ選び、その教科について生徒 $j$ と比較しなければならない。生徒 $i$ が条件を評価する際、比較対象となるすべての $j$ に対して同じ教科を用いなければならない。生徒 $i$ の条件を評価している途中で教科を切り替えることはできない。

新しいクラス順位の不満度は、すべての生徒の中での順位の最大の低下として定義される。言い換えれば、不満度はすべての $0 \leq i \leq N - 1$ についての $P[i] - i$ の最大値である。

警告 不満度は $P[i] - i$ の最大値であり、$i - P[i]$ の値は不満度に影響しない。

新しいクラス順位の不満度の最小値を求めよ。

実装の詳細

以下のプロシージャを実装すること。

int minimum_dissatisfaction(int N, std::vector<int> A, std::vector<int> B)

• $N$: 生徒の人数。
• $A$: 英語試験の順位を表す長さ $N$ の配列。
• $B$: 数学試験の順位を表す長さ $N$ の配列。
• このプロシージャは、新しいクラス順位の最小不満度を返す必要がある。
• このプロシージャはちょうど一度だけ呼び出される。

制約

• $1 \leq N \leq 5\;000\;000$
• $0 \leq A[i], B[i] \leq N - 1$ (すべての $0 \leq i \leq N - 1$ について)
• $A[i] \neq A[j]$ (すべての $0 \leq i < j \leq N - 1$ について)
• $B[i] \neq B[j]$ (すべての $0 \leq i < j \leq N - 1$ について)

小課題

1. (3点) $N \leq 8$
2. (4点) $N \leq 20$
3. (13点) $N \leq 500$
4. (12点) $N \leq 3000$、すべての $0 \leq i \leq N - 1$ について $A[i] + B[i] = N - 1$
5. (19点) $N \leq 3000$
6. (15点) $N \leq 100\;000$、すべての $0 \leq i \leq N - 1$ について $A[i] + B[i] = N - 1$
7. (17点) $N \leq 100\;000$
8. (17点) 追加の制約なし

注記: 小課題8については、グレーダー単体で制限時間 3000ms のうち 1500ms を消費することが保証されている。

入出力例

以下の呼び出しを考える。

minimum_dissatisfaction(5, [3, 0, 4, 1, 2], [0, 3, 2, 4, 1])

この例では、新しい順位の割り当て方の一つとして $P = [0, 2, 3, 4, 1]$ がある。

$P[1] = 2$ である生徒 $1$ を考える。$P[j] < P[1]$ を満たすすべての生徒 $j$ は、生徒 $1$ よりも数学の順位が良い。したがって、この生徒はクラス順位の条件を満たしている。

次に、$P[2] = 3$ である生徒 $2$ を考える。$P[j] < P[2]$ を満たすすべての生徒 $j$ は、生徒 $2$ よりも英語の順位が良い。したがって、この生徒もクラス順位の条件を満たしている。

他のすべての生徒についても、クラス順位の条件を満たしていることが確認できる。

新しい順位の不満度は $1$ である。これより低い不満度を持つ新しい順位は存在しないため、このプロシージャは $1$ を返す必要がある。

サンプルグレーダー

入力形式:

N
A[0] A[1] ... A[N - 1]
B[0] B[1] ... B[N - 1]

出力形式:

minimum_dissatisfaction の戻り値を表す整数。