Шоколад
Шоколад
Шоколад, который производит кондитерская компания «Ням Ням», имеет вид длинной плитки 1хN, состоящей из N квадратиков. На каждом квадратике изображен один из N известных кондитеров, причем на разных шоколадках, которые производит компания, изображены одни и те же N кондитеров, только в разном порядке.
Задание Напишите программу, которая для заданного порядка портретов на двух плитках шоколада определяет, на какое наименьшее количество частей придется разломать первую плитку, чтобы путем переставления частей из нее можно было образовать вторую. Ломать плитку разрешается только по границам квадратиков, а переворачивать плитку или ее части нельзя.
Входные данные Первая строка входного файла содержит натуральное число N (2 ≤ N ≤ 10^5), задающее размер плитки шоколада, то есть количество квадратиков в ней. Все кондитеры пронумерованы числами от 1 доN. Вторая и третья строки файла содержат по N разных натуральных чисел каждая (все числа не превосходят N) — порядок портретов на первой и второй плитках соответственно. Известно, что эти порядки различны.
Çıxış verilənləri
Ввыходной файл следует вывести одно число — наименьшее количество частей, на которые придется разломать первую плитку так, чтобы, каким-то образом переставив эти части местами, получить порядок портретов на второй плитке.
Nümunə
5 4 3 2 5 1 1 2 5 3 4
4
Qiymətləndirmə
Набор тестов состоит из 4 блоков, для которых дополнительно выполняются такие условия:
20 баллов: 2 ≤ N ≤ 3
20 баллов: 3 < N ≤ 6
30 баллов: 6 < N ≤ 1000
30 баллов: 1000 < N ≤ 10^5
Пояснение. Первую плитку можно разломать на такие четыре части: квадратик 4, квадратик 3, два квадратика 2 и 5, квадратик 1. Переставив эти части местами нужным образом, получим такой же порядок портретов, как и на второй плитке. В то же время ни один из способов разламывания на три или две части не позволит получить такой же порядок портретов, как на второй плитке.