eolymp
bolt
Try our new interface for solving problems
Məsələlər

Календарь

Календарь

Учёные-археологи планеты Олимпия нашли две пещеры с признаками пребывания доисторических племен. Их внимание привлекли n различных слов, начертанных на стене в каждой из пещер. Интересно, что эти слова в обеих пещерах оказались одинаковыми, но выписанными в разной последовательности. Учёные выяснили:

  1. Начертанные слова - это названия месяцев года, которые перечислены в порядке наступления у соответствующего племени.
  2. Год у племён был разбит на n месяцев равной продолжительности, а дни начала месяцев совпадали.

Однако, учёные так и не определили, в какой месяц начинался год у каждого из племен.

Напишите программу, которая по данным о последовательности названий месяцев в обеих пещерах, найдет наибольшее количество месяцев, которые могли бы иметь одинаковые названия у обоих племен, учитывая, что год у племён мог начинаться в разные моменты времени. Для упрощения анализа учёные сопоставили каждому из названий месяцев свой номер - натуральное число от 1 до n.

Входные данные

Состоит из трех строк. В первой строке содержится натуральное число n (2n105) - количество названий месяцев, начертанных на стене каждой из пещер. Вторая строка содержит n различных натуральных чисел, каждое из которых не превышает n - номера слов в порядке, в котором они начертаны в первой пещере. Третья строка также содержит n различных натуральных чисел, каждое из которых не превышает n - номера слов в порядке, в котором они начертаны во второй пещере.

Выходные данные

Вывести одно число - наибольшее количество месяцев, которые могли бы называться одинаково у обоих племен.

_Пояснение к первому примеру:_ Если год у второго племени начинается, например, на месяц позже, чем у первого, то два месяца имеют у племен одинаковые названия (номер 1 и 4):

prb4972-ru

Никакая другая комбинация не приводит к совпадению большего количества названий месяцев.

_Пояснение ко второму примеру:_ Независимо от того, когда именно у племен начинается год, одинаковое название всегда будет иметь только один месяц.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
4
2 4 3 1
4 2 1 3
Çıxış verilənləri #1
2
Giriş verilənləri #2
3
3 2 1
1 2 3
Çıxış verilənləri #2
1
Müəllif Daniil Mysak
Mənbə 2013 XXVI All-Ukrainian Informatics Olympiad, Lugansk, March 17 - 21, Round 1