Có $N$ học sinh trong một lớp học. Mỗi học sinh được gán một số từ $0$ đến $N - 1$ dựa trên thứ hạng hiện tại trong lớp. Cụ thể, học sinh $i$ (với mọi $0 \le i \le N - 1$) hiện có thứ hạng $i$. Ở đây, hạng $0$ là tốt nhất và hạng $N-1$ là tệ nhất.

Các kỳ thi Tiếng Anh và Toán vừa được tổ chức. Học sinh $i$ (với mọi $0 \le i \le N - 1$) đạt hạng $A[i]$ trong môn Tiếng Anh và $B[i]$ trong môn Toán. $A$ và $B$ là các hoán vị có độ dài $N$.

Hoán vị có độ dài $N$ là gì? Trong bài toán này, một hoán vị $P$ có độ dài $N$ là một mảng có độ dài $N$ sao cho $0 \leq P[i] \leq N-1$ với mọi $0 \leq i \leq N-1$ và $P[i] \neq P[j]$ với mọi $0 \leq i < j \leq N-1$. Ví dụ, $[2,1,0]$ là một hoán vị có độ dài $3$, nhưng $[1,2,3]$ và $[2,0,2]$ không phải là các hoán vị có độ dài $3$.

Giáo viên muốn xếp lại thứ hạng cho các học sinh. Thứ hạng mới có thể được biểu diễn bằng một hoán vị $P$.

Với mỗi học sinh $i$, thứ hạng mới phải thỏa mãn ít nhất một trong các điều kiện sau:

• Với mọi $j$ sao cho $P[j] < P[i]$, học sinh $j$ giỏi hơn học sinh $i$ trong môn Tiếng Anh ($A[j] < A[i]$), HOẶC
• Với mọi $j$ sao cho $P[j] < P[i]$, học sinh $j$ giỏi hơn học sinh $i$ trong môn Toán ($B[j] < B[i]$).

Cảnh báo: Điều kiện chỉ áp dụng cho các $j$ sao cho $P[j] < P[i]$. Không có ràng buộc nào cho các $j$ sao cho $P[j] \geq P[i]$. Với mỗi học sinh $i$, khi đánh giá xem điều kiện có được thỏa mãn hay không, học sinh đó phải chọn một môn học và đánh giá môn học đó so với các học sinh $j$. Môn học mà tại đó $j$ giỏi hơn học sinh $i$ phải giống nhau cho các $j$ khác nhau, với cùng một $i$. Bạn không thể thay đổi môn học khi đang đánh giá điều kiện cho học sinh $i$.

Sự bất mãn của thứ hạng mới được định nghĩa là mức tụt hạng lớn nhất trong tất cả các học sinh. Nói cách khác, sự bất mãn là giá trị lớn nhất của $P[i] - i$ (với mọi $0 \le i \le N - 1$).

Cảnh báo: Sự bất mãn là giá trị lớn nhất của $P[i] - i$, các giá trị $i - P[i]$ không ảnh hưởng đến sự bất mãn.

Hãy tìm sự bất mãn nhỏ nhất có thể của thứ hạng mới.

Chi tiết cài đặt

Bạn cần cài đặt thủ tục sau:

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

• $N$: số lượng học sinh.
• $A$: một mảng có độ dài $N$ mô tả thứ hạng của kỳ thi Tiếng Anh.
• $B$: một mảng có độ dài $N$ mô tả thứ hạng của kỳ thi Toán.
• Thủ tục này trả về sự bất mãn nhỏ nhất của thứ hạng mới.
• Thủ tục này được gọi chính xác một lần.

Giới hạn

• $1 \leq N \leq 5\;000\;000$.
• $0 \leq A[i], B[i] \leq N - 1$, với mọi $0 \leq i \leq N - 1$.
• $A[i] \neq A[j]$, với mọi $0 \leq i < j \leq N - 1$.
• $B[i] \neq B[j]$, với mọi $0 \leq i < j \leq N - 1$.

Nhiệm vụ con

1. (3 điểm) $N \leq 8$.
2. (4 điểm) $N \leq 20$.
3. (13 điểm) $N \leq 500$.
4. (12 điểm) $N \leq 3000$, $A[i] + B[i] = N - 1$ với mọi $0 \leq i \leq N - 1$.
5. (19 điểm) $N \leq 3000$.
6. (15 điểm) $N \leq 100\;000, A[i] + B[i] = N - 1$ với mọi $0 \leq i \leq N - 1$.
7. (17 điểm) $N \leq 100\;000$.
8. (17 điểm) Không có ràng buộc bổ sung.

Ghi chú: đối với nhiệm vụ con 8, riêng trình chấm (grader) đã được đảm bảo tiêu tốn 1500ms trong giới hạn thời gian 3000ms.

Ví dụ

Xét lời gọi sau:

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

Trong ví dụ này, một cách để gán thứ hạng mới là $P = [0, 2, 3, 4, 1]$.

Xét học sinh $1$ với $P[1] = 2$. Tất cả các học sinh $j$ có $P[j] < P[1]$ đều có thứ hạng Toán tốt hơn học sinh $1$, vì vậy học sinh này thỏa mãn điều kiện xếp hạng.

Tiếp theo, xét học sinh $2$ với $P[2] = 3$. Tất cả các học sinh $j$ có $P[j] < P[2]$ đều có thứ hạng Tiếng Anh tốt hơn học sinh $2$, vì vậy học sinh này cũng thỏa mãn điều kiện xếp hạng.

Có thể kiểm tra tất cả các học sinh khác rằng họ cũng thỏa mãn điều kiện xếp hạng.

Sự bất mãn của thứ hạng mới là $1$. Không có thứ hạng mới nào khác có sự bất mãn thấp hơn, vì vậy thủ tục nên trả về $1$.

Trình chấm mẫu

Dữ liệu vào:

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

Dữ liệu ra:

Một số nguyên đại diện cho giá trị trả về của minimum_dissatisfaction.