Trong một tình huống có vẻ quen thuộc, Farmer John đang xếp hàng \(N\) con bò (\(1\le N\le 10^5\)), được đánh số thuận tiện từ \(1\ldots N\), để chụp ảnh.

Ban đầu, từ trái sang phải, các con bò đứng theo thứ tự \(a_1,a_2,\ldots,a_N\). Mục tiêu của Farmer John là xếp chúng theo thứ tự \(b_1,\ldots,b_N\) từ trái sang phải. Để làm được điều này, ông có thể thực hiện một chuỗi lần thay đổi thứ tự. Mỗi lần thay đổi gồm việc chọn một con bò duy nhất và dịch nó sang trái một số vị trí.

Hãy tính số lần thay đổi ít nhất cần thiết để Farmer John xếp đàn bò theo thứ tự mong muốn.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Dòng thứ hai chứa \(a_1,a_2,\ldots,a_N\). Dòng thứ ba chứa \(b_1,b_2,\ldots,b_N\).

Dữ liệu ra

In số lần thay đổi ít nhất cần thiết để tạo ra thứ tự Farmer John mong muốn.

Phân nhóm

• Các test 3–6 thỏa mãn \(N\le 100\).
• Các test 7–10 thỏa mãn \(N\le 5000\).
• Các test 11–14 không có ràng buộc bổ sung.

Ví dụ

5
1 2 3 4 5
1 2 3 4 5

0

5
5 1 3 2 4
4 5 2 1 3

2

   5 1 3 2 4
-> 4 5 1 3 2
-> 4 5 2 1 3

Nguồn

USACO 2022 February Contest, Bronze — Photoshoot 2: https://usaco.org/index.php?page=viewproblem2&cpid=1204

Tác giả: Benjamin Qi.