Задача №112110. Календарь
Ученые-археологи планеты Олимпия нашли две пещеры с признаками пребывания доисторических племен. Их внимание привлекли N различных слов, начертанных на стене в каждой из пещер. Интересно, что эти слова в обеих пещерах оказались одинаковыми, но выписанными в разной последовательности. Ученые выяснили:
- Начертанные слова — это названия месяцев года, которые перечислены в порядке наступления у соответствующего племени.
- Год у племен был разбит на N месяцев равной продолжительности, а дни начала месяцев совпадали.
Однако, ученые так и не определили, в какой день начинался год у каждого из племен.
Напишите программу, которая по данным о последовательности названий месяцев в обеих пещерах найдет наибольшее количество месяцев, которые могли бы иметь одинаковые названия у обоих племен, учитывая, что год у племен мог начинаться в разные моменты времени. Для упрощения анализа ученые сопоставили каждому из названий месяцев свой номер — натуральное число от 1 до N .
Входной файл состоит из трех строк. В первой строке содержится натуральное число N ( 2 ≤ N ≤ 10 5 ) — количество названий месяцев, начертанных на стене каждой из пещер. Вторая строка содержит N различных натуральных чисел, каждое из которых не превышает N , — номера слов в порядке, в котором они начертаны в первой пещере. Третья строка также содержит N различных натуральных чисел, каждое из которых не превышает N , — номера слов в порядке, в котором они начертаны во второй пещере.
Выходной файл должен содержать единственное число — наибольшее количество месяцев, которые могли бы называться одинаково у обоих племен.
Пояснение к первому примеру:
Если год у второго племени начинается, например, на месяц позже, чем у первого, то два месяца имеют у племен одинаковые названия (номер 1 и 4):
Племя 1: 3 1 2 4 3 1 2 4 3 1 2 4
Племя 2: 2 1 3 4 2 1 3 4 2 1 3 4
Никакая другая комбинация не приводит к совпадению большего количества названий месяцев.
Пояснение ко второму примеру:
Независимо от того, когда именно у племен начинается год, одинаковое название всегда будет иметь только один месяц.
4 2 4 3 1 4 2 1 3
2
3 3 2 1 1 2 3
1