Chụp Ảnh 2

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John đang sắp xếp $N$ con bò (đánh số từ $1$ đến $N$ ) cho buổi chụp ảnh. Hiện tại các con bò đang đứng theo thứ tự $a_{1}, a_{2}, \dots, a_{N}$ và cần được sắp xếp lại thành thứ tự $b_{1}, b_{2}, \dots, b_{N}$ .

Thao tác duy nhất được phép là chọn một con bò và di chuyển nó sang trái một số vị trí bất kỳ (ít nhất 1 vị trí).

Hãy tìm số thao tác tối thiểu cần thực hiện.

Dữ liệu vào

Dòng 1: Số nguyên $N$
Dòng 2: $N$ số nguyên $a_{1}, a_{2}, \dots, a_{N}$ — thứ tự hiện tại
Dòng 3: $N$ số nguyên $b_{1}, b_{2}, \dots, b_{N}$ — thứ tự mong muốn

Dữ liệu ra

Một số nguyên — số thao tác tối thiểu.

Ràng buộc

$1 \leq N \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
5 1 2 3 4 5 1 2 3 4 5	0	Đã đúng thứ tự.
5 5 1 3 2 4 4 5 2 1 3	2	Di chuyển bò 4 sang trái 4 vị trí, sau đó di chuyển bò 2 sang trái 2 vị trí.

Bình luận

Không có bình luận tại thời điểm này.