Шоколад#7253
Шоколад, який виробляє кондитерська компанія «Ням Ням», має вигляд довгої плитки 1\times N, що складається з квадратиків. На кожному квадратику зображено одного з відомих кондитерів. На різних шоколадках, які виробляє компанія, зображено одних й тих самих кондитерів, але в різному порядку.
Завдання. Напишіть програму, що для заданого порядку портретів на двох плитках шоколаду визначає, на яку найменшу кількість частин доведеться розламати першу плитку, щоб переставлянням частин із неї можна було утворити другу. Ламати плитку можна тільки по межах квадратиків, а перевертати плитку чи її частини не можна.
Перший рядок вхідного файлу містить натуральне число (2 \le N \le 10^5), що задає розмір плитки шоколаду, тобто кількість у ній квадратиків. Кондитерів занумеровано числами від до . Другий та третій рядки містять по різних натуральних чисел кожен (усі числа не перевищують ) — порядок портретів відповідно на першій і на другій плитках. Відомо, що ці порядки різні.
Вихідний файл має містити єдине число — найменшу кількість частин, на які доведеться розламати першу плитку так, щоб, якимось чином переставивши ці частини, отримати порядок портретів на другій плитці.
Приклад 1
Першу плитку можна розламати на чотири частини: квадратик , квадратик , два квадратики і , квадратик . Потрібним чином переставивши ці частини, отримаємо такий самий порядок портретів, як і на другій плитці. Жоден спосіб розламування на три або дві частини не дозволить скласти такий самий порядок портретів, як на другій плитці.
Набір тестів складається з 4 блоків, для яких додатково виконуються такі умови:
20 балів: 2 \le N \le 3
20 балів: 3 < N \le 6
30 балів: 6 < N \le 1000
30 балів: 1000 < N \le 10^5